Linked Lists

A linked list is a data structure that uses pointers to point to the next item in the list. A linked list can be implemented using an array or using a class.

Linked List

Item Added to List

A linked list is a kind of list where each item in the list has two parts: its content, and a pointer to the next item in the list. This means it can grow dynamically and there is no restriction on its size.

A linked list does not have a fixed size and therefore it allocates memory to the next item in the list as and when it needs it. When a location is needed, it is pulled from a pool of all the available main memory locations in main memory called the heap. When they are no longer required, the locations can be returned to the heap for use by other applications. This operation is known as “freeing” the pointer.

The name given to a pointer represents the location that contains the address of the location you are using – you never know the address of the location being referenced; the pointer finds it for you from the heap.

Here is a simple implementation of a linked list using a class:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Node:
    def __init__(self, contents=None, next=None):
        self.contents = contents
        self.next  = next

    def getContents(self):
        return self.contents

    def __str__(self):
        return str(self.contents)

def print_list(node):
    while node:
        print(node.getContents())
        node = node.next
    print()

def testList():
    node1 = Node("car")
    node2 = Node("bus")
    node3 = Node("lorry")
    node1.next = node2
    node2.next = node3
    print_list(node1)

Download the program.


Exercises

  1. Implement the simple linked list given above.
  2. Add the functionality to add an item part way through the list
  3. Add the functionality to delete an item from the list