Demystifying Linked Lists

A linked list is an interesting and fundamental data structure often introduced in the first year of computer science curriculums. These usually serve to demonstrate basic concepts in data structures and algorithms.

For a full video on the mechanics of linked lists, see below:

To download basic Linked List code in Java, please refer to the following link: https://drive.google.com/open?id=0B2Ia5aQpQ8CnVWI5eWV3VzJod0k

Fundamentals of Linked Lists

A linked list contains any number of nodes. Each node carries one unit of data, and also contains a reference or pointer to the next value.

This allows you to build sequences of information, similar to an array, but not bound by its limitations (eg. Arrays have fixed length).

However, due to the linked node nature of Linked Lists, operations on a list may require a bit more thought. Failure to implement them properly could lead to loss of contained data.

Let’s consider some operations that can be performed on Linked Lists.

Read and Traversal

A linked list can be accessed via its first node, also known as the “head”. As such, linked list implementations must keep track of the memory location of the head node.

To find node n, the following steps must be taken:

  1. Maintain a count i, starting at zero
  2. While i is less than n, keep traversing forward
  3. If the traversal step above leads to a nonexistent node, give an error as the desired node does not exist
  4. If the loop ends, the current item is the desired item, and can be returned to the user

Insertion

A new item may be inserted at any position in the list, including at the head or at the very end. The former requires special care as the head of the linked list must be updated (not doing so results in “loss” of the first element).

The procedure is as such:

  1. If the new item is to be inserted at the head of the list:
    • Point the new item to the current head of the list
    • Point the head of the list to the new item
    • End the procedure

  2. If the new item is to be inserted anywhere else, traverse to the item one position prior to the desired position (see “Read and Traversal” above)
  3. Point the new item to the next item as indicated by the current node (could be null, that’s fine)
  4. Point the current item to the new item

Deletion

The concerns behind deletion are very similar to that of insertion. In particular, if the deleted item is at the head, the head needs to be updated.

  1. If the item to be deleted is at the head of the list:
    • Set the head to the next item indicated by the head
    • End the procedure

  2. If the deletion is anywhere else, traverse to the item one position prior to the desired position (see “Read and Traversal” above)
  3. Check the item to be deleted (reachable from the current item), and ensure that it exists
  4. Set the current item to the item two positions after it

Pros and Cons

A linked list provides some advantages over a simpler data structure like an array, including:

  • Non fixed length
  • Does not require a contiguous space in RAM
  • Insertion and deletions at arbitrary positions allowed without having to shift all existing items

However, some disadvantages are also clear, as linked Lists can only be traversed item by item from the head. This leads to:

  • Poor performance when finding items in the middle or end of list
  • Very poor performance if each item needs to be visited in turn

Both of the above can be worked around if additional functions are written, but this means additional effort is required to add functionality that would have otherwise been already present for arrays. However, some extensions of Linked Lists are indeed used out there. Examples include the Circular Linked List or Doubly Linked List.

Despite the complex sounding nature of Linked Lists, they’re a fun learning tool and have their application in the real world. Hopefully the images and writeup above can allay your fears on using them! Again, you can download some sample code here.

That’s all for this post! If you like my work and wish to support me, I’ll greatly appreciate a one-time or recurring donation!