Linked Lists

One of the problems with using an array is that it is not truly dynamic. This is because when an array is declared a set of continuous locations in memory are assigned to the array on the heap. Increasing the size would require declaring another larger set of locations on the heap and copying all the data to the new locations. This is a resource hungry operation!

An alternative method of implementing a list is to create a linked list.

How it Works

Each item in a linked list is a set of data pairs (called nodes) containing the data to be stored and a pointer to the next item in the list.

There is then a structure that holds information about the list:

  • a count of the number of items in the list

  • a pointer to the first item in the list (the head of the list)

  • a pointer to the last item in the list (the tail of the list)

As items are added to the list the previous node is set to point to the new item. The Linked List also updates it's pointer to the tail.

Each node is declared on the heap so is a reference object. If there is nothing pointing to a node, then it will be removed from the heap.

Adding items to a list

To add to the list:

  • We first need to create a new list node to hold the data.

  • We then point the current last node in the list to the new node.

  • We then tell the list that the new node is the last node.

  • Increment the count

Create the new list node

Point the current last node to the new node.

Finding Items in a list

Similar to an array list, each item must be checked in turn. The difference being that instead of using a variable as an index to determine which element to inspect next, we follow the chain (counting each link to establish the index).

Removing Items from a list

To remove items from the list we need to:

  • Go through each node checking to see if the next item is the item to be removed.

  • If it is, point the current node to the next node of the node to be removed.

  • Remove 1 from the count.

The removed node no longer has any references to it, so the computer removes it from the heap during the next garbage collection.

Inserting Items into a list

The order of the instructions is very important so you don't loose part of the list...

  • Create a new list node to hold the data

  • Find the place in the list where the new node will be inserted.

  • Point the new node to the next node.

  • Point the previous node to the new node instead of the next node.

  • Increment the count.

Create a new list node and point to the next node

Point the node that will be in front to the new list node.

Advantages and Disadvantages of using a Linked List

Advantages

  • It is a dynamic data structure, able to grow and shrink at runtime. This makes it more memory efficient because you only allocate the memory needed to hold the data for the time needed to hold it.

  • Inserting or removing items from the list is more efficient than using an array because you do not need to shift or copy other data items.

Disadvantages

  • Random access to nodes is not possible - you must traverse the list.

  • Traversing a list is slow because you must visit each previous node.

  • A Linked list takes up more space than an array for the same amount of data because it must also store the pointers.

  • The is a small cost in time when adding nodes because the new node needs to be declared on the heap and the memory allocated.