Data Structures: Linked List

In Software Engineering 101, the first data structure that we’re going to look at is the Linked List. As the name says, the Linked List is a list which consists of a sequence of accessible nodes. It’s both a simple and common data structure that can be used as an approach for implementations of queues, stacks, lists and associative arrays.

But why would we not just use an array for this anyway?

  • Well, to begin with Arrays are of a fixed size meaning memory must be allocated for the specified size upon initialisation. However, Linked Lists allocate memory at runtime for the amount that is required (due to it being a dynamic data structure).
  • If we wish to add a new item at the end of our array then this can be an issue if the array is full. If so, this would mean creating a whole new array of a larger size and copying over the values. In a Linked List however, we can simply add a new node and adding a reference to it from the previous last node in the list.
  • If we want to insert a new item at a position somewhere in the middle of our Array then that can be an expensive task, this is because we have to shift all items after the new position of the new value one position to the right – if our array is very big then this is quite inefficient. However, with a linked list we only need to update the neighbouring nodes of the position in which we want to insert the new node – this is simply between 2 and 4 references depending on the type of Linked List.

However, there are obviously some disadvantages with Linked Lists:

  • If searching for an item, then we cannot access elements by index reference. We must iterate through the entire list, which could involve iterating a lot of items to find the desired one.
  • The use of pointers increases the use of memory usage as they cause the operation to require more storage to operate.
  • Traversing lists in a reverse order can be a little bit of a pain to do. The issue is slightly relieved when using a doubley linked list (more on this below), but this involves the additional memory overhead with the use of a previous pointer per node.

Types of Linked List

Depending on our requirements, there is more than one type of Linked List which we can implement. This can be one of:

Singly Linked List


In a singly linked list, the nodes only have a pointer to the next item in the list. They are not aware of the previous item as there is no reference to it. In this case, the nodes only have a one way relationship with their neighbour.

Circular Singly Linked List


This approach is the same as a standard Singly Linked List, but with the addition of the last nodes next property holding a reference to the first node in the list.

Doubly Linked List


On the other hand, a doubly Linked list does have a reference to both the next and previous nodes. In this case, the nodes have a two way relationship with their neighbouring nodes.

Circular Doubly Linked List


The circular doubly linked list is the same as the double linked list, but with two additions:

  • Like the circular singly linked list, the next property of the last node points to the first node in the list.
  • The previous property of the first node in the list points to the last node in the list.

Creating a Linked List

Before we begin looking at the different operations of a Linked List, lets look at the implementation of a simple Singly Linked List:

struct node_struct
{
int val;
struct node_struct *next;
};

struct node_struct *head = NULL;
struct node_struct *curr = NULL;

struct node_struct* create_list(int val) {
struct node_struct *ptr =
(struct node_struct*) malloc(sizeof(struct node_struct));
if (ptr == null) return NULL;
    ptr->val = val;
ptr->next = NULL;

head = curr = ptr;
return ptr;
}

What’s happening here is:

  • We define the node structure, which consists of an int value and a reference to the next node in the list.
  • We then define the create_list function which takes the initial value to be used for our linked list. In this function, we created a new node instance and assign the value to the val parameter. We set the next reference to null (as there’s no next node) and set the head of our list to this first item that we’ve created.

Now we have a list created, we are able to make other functions which we can use to both view and amend our list of data.

Accessing Nodes

If we want to access these nodes within our linked list then we are required to do so by iterating through the elements. I.e We must iterate through N elements if we with to access the Nth element. If we wanted to write some pseudocode for this operation, it would look as follows:


The worst case time in which this would complete is O(n) time. This is because there are n number of elements and we may have to search the entire list to find the desired item.

To understand this a little more, let’s implement this with some code. So as an example, if we wish to loop through the contents of our Linked List then we could do as follows:

void iterateList() {
struct node *ptr = head;

if(head != NULL) {
while(ptr->next != ptr) {
printf("(%d, %d) ", ptr->key, ptr->data);
ptr = ptr->next;
}
}
printf("Looks like your list could be empty...");
}

In this simple example you can see that:

  • We begin by creating a pointer referencing the start (head) of our list.
  • Then, whilst the next reference of the current node
  • We print the contents of the node and set the pointer reference to the next node in the list.

Iterating through a list

But what about accessing a specific item in our list? We still have to iterate through the list, but only up to the point where we reach out element. We can do this like so:

int getItem(struct node* head, int index) {
struct node* ptr = head;
int count = 0;
while (ptr != NULL) {
if (count == index) return(ptr->data);
count++;
ptr = ptr->next;
}
assert(0);
}
  • We begin by starting the function at the head of our list, we need to iterate through the whole list so we must start at the beginning.
  • Next, we declare a count variable which again starts at index 0. This is so we can keep a reference to the index that we are currently at in the list.
  • We begin the loop here. Whilst looping, if the count variable is equal to the index parameter then it means we’re at the index that we wished to retrieve – so we return the node’s data.
  • Otherwise, we increment count (to be the next index) and sent the pointer to reference the next node in the list.
  • If we do all of this and our index has still not been found, then the assert() statement declares that there was access to a non-existent element.

Getting a node from a specific position in a list

Removing a node

When removing a node from the List, we need to update the reference(s) that exist between nodes. Using pseudocode, let’s first take a look at an example:


So in this example, x is the Node we have previously retrieved reference to and wish to delete, s0:

  • We begin by finding the previous node of n and set it’s next property to the next property of node N.
  • Here we’re dealing with a doubley Linked list implementation, then we must set the previous property of the next node of node N to the previous node of node N.

This pseudocode would complete in O(1) time as we already have the node in which we wish to delete. If we didn’t, we’d first have to search for it and then delete it – this would increase the completion time to O(n).

If we wanted to implement this in code, then we could do it like so:

void deleteNode(struct node *head, struct node *n) {
    if(head == n) {
if(head->next == NULL) return;
        head->data = head->next->data;
n = head->next;
head->next = head->next->next;
        free(n);
return;
}
    struct node *prev = head;
while(prev->next != NULL && prev->next != n) prev = prev->next;
if(prev->next == NULL) return;
prev->next = prev->next->next;
    free(n);
return;
}

What’s going on here?

  • We begin by checking if the head node is equal to the n node parameter we have passed in.
  • If this is the case and the head doesn’t have a reference to a next node, then we return as we can’t delete the only node in the list.
  • Otherwise, we set the data value of the head node to the data value of the next node. We then store the address of the next node (so we don’t lose reference to it) and set the next reference of the head node to point to the node after the next node. We then free memory of n (the node we kept a reference to) and return as the operation has completed.
  • However, if our n node is not equal to the head node then we need to find the node it is that we wish to delete. We do this we begin by looping through our items until we reach the item whos next reference points to the node we wish to delete (n).
  • When this is satisfied, the loop breaks with prev set to the node previous to the one we wish to delete.
  • Now we have reference to the node previous to the node we wish to delete, we remove the node by setting the next reference of this node to the node after the node we’re deleting. Now the node we wished to delete has no references being made to it, so it’s been removed.

Removing a node from the list

And that’s it!

We’ve learnt what a Linked List, where it may be used and the different kind of Linked Lists that we can implement. We’ve also looked at some operations which we can carry out with them, bearing their complexities in mind. Whether you’re learning from scratch or refreshing your knowledge on data structures, I hope this deep-dive has been a good companion in understanding how Linked Lists operate.

If you have any questions, feel free to to leave a response or drop me a tweet!

Check out more of my projects at hitherejoe.com

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s