Data Structures – Linked List

Hi All! ๐Ÿ™‚

In a similar vein to my recent post regarding Dynamic Array data structure I am here today to demonstrate my implementation of an Ordered Linked List. This linked list is a bit more complicated than the Dynamic Array we created but I will endeavour to explain it as simply as I can.

A Linked List is used to hold data in a sequential but not contiguous form. Similar to the Dynamic Array we created earlier we can add and remove elements easily but to access a node in a Linked List we need to step through the entire structure until we have found the element we wanted. This results in access being O(n) which is slower than the Dynamic Array’s O(1) access. The advantage however is that insertion and deletion of elements are much easier. With the Dynamic Array we had to copy the entire array for each insertion and deletion. For the Linked List we only need to find the element we want and then delete it using the algorithm described below, there is no need to change the rest of the structure.

For a more detailed explanation of Linked Lists visit the Wikipedia page. Anyway, let’s move into the actual implementation.

OrderedList Class

Source Code

Here are the complete source code files for our test implementation of the Linked List:

You can also access the source on GitHub: https://github.com/gabeb1920/OrderedList

Note that I have created this as a template class so it is capable of holding any data type. You can even use your own classes however note that they will need an overloaded assignment operator(=), less than comparison operator(<) and output operator(<<) to use this data structure.

OrderedList.h

Our Ordered List is made up of 2 pointers to ListNodes called head and tail. These represent the beginning and end of the list. Before we move into the methods of our OrderedList class let’s look at the ListNode class.

ListNode Class

This class contains 3 data elements:

  • T data
    • The actual data.
  • ListNode * next
    • A pointer to the next node.
  • ListNode * prev
    • A pointer to the previous node. This makes our implementation a doubly linked list though I don’t end up using any of the features this includes. For all intents and purposes this is a singly linked list.

We include a simple constructor and destructor as well as functions for setting and getting each data element. All are fairly straight forward and simple so we won’t go into any more detail on these ones.

  • Constructors/Destructors
    • ListNode()
    • ~ListNode()
  • Set Functions
    • void setPrev(ListNode * newPrev)
    • void setNext(ListNode * newNext)
    • void setData(T newData)
  • Get Functions
    • ListNode * getPrev()
    • ListNode * getNext()
    • T getData()

OrderedList Class

This is where things get a bit more interesting!

As we already mentioned the OrderedList class only contains 2 data elements:

  • ListNode<T> * head
    • A pointer to the start of the list.
  • ListNode<T> * tail
    • A pointer to the end of the list. As with the ListNode class this is superfluous. It could be used to traverse the List in reverse or to improve the search, insertion and deletion functions but I haven’t done that here. Feel free to do so in your own implementation though. ๐Ÿ™‚

The OrderedList also has the following methods:

  • Constructors/Destructor
    • OrderedList()
    • OrderedList(OrderedList<T> & newOL)
      • This is the copy constructor used for passing by value. This is implemented by stepping through the newOL list and inserting each data element into the new list.
    • ~OrderedList()
      • Here we step through the list and delete each element one by one. The only trick is to remember to note the next node before deleting the current node. Otherwise you won’t be able to access the deleted node to get the next!
  • Other Functions
    • ListNode<T> * begin()
      • Simply returns a pointer to the head of the list.
    • ListNode<T> * end()
      • As is traditional with the end function this version simply returns NULL. Rather than point to the beginning of the last node in the list the end function points to the end of the last node which is NULL.
    • void insert(const T & newData)
    • void remove(const T & oldData)
    • ListNode<T> * exists(const T & data)
      • Simply steps through the list and returns a pointer to the first node which contains the data element requested.
  • ย Overloaded Operators
    • friend ostream & operator<<(ostream & out, const OrderedList<U> rhs)
      • Used to print out each data element from each ListNode, one per line.

Let’s have a look at some of these methods in a bit more detail.

void insert(const T & newData)

To insert a new node into a linked list we create a temporary ListNode<T> and set the data to the newData parameter. Then we check if the head is currently NULL. If it is then we can insert the new node as the head. If the head is not NULL then in a traditional linked list we would then step through the list until we reach the end where the next pointer = NULL. We would change the last element’s next pointer to point to the newly created node and then we’re done.

As we are implementing an ordered list it is a bit more complicated. First we need to find the position where the new node will be inserted. We do this by stepping through the list until we find a node which is bigger than the new node. So the new node will be inserted just before the node we’ve just found. The only special case is if we reach the end of the list. This means that the new node is our new tail and so we need to change the tail of the list to point to the new node as well as insert the new node into the list.

To insert the new node we need to set the new node’s details and change both the node before and after the new node.

      • new node’s next = node before’s next
      • new node’s previous = node before
      • node before’s next = new node
      • node after’s prev = new node

And then we’re done! No need to copy the entire list as with the Dynamic Array. We simply create the new node and change 4 pointers.

void remove(const T & oldData)

Removing a node is similar to inserting, we need to find the element we are looking for, change the previous and next node’s pointers and then delete the found node.

  • node before’s next = found node’s next
  • node after’s prev = found node’s prev
  • Delete found node
  • Done!

Summary

The Linked List data structure is commonly used throughout programming whether behind the scenes in a library or if you implement a customised structure yourself. It is also common to be asked questions about Linked Lists in coding interviews so it’s always good to review the details of their use and implementation. I hope you find this post useful.

What changes would you make to this implementation? Have you had any interesting cases where you’ve used Linked Lists? Let me know in the comments.

Until next time! ๐Ÿ™‚

2 thoughts on “Data Structures – Linked List

Leave a Reply

Your email address will not be published. Required fields are marked *