Coding Data Structures: Linked Lists

Let’s cover a basic coding data structure: linked lists. Linked lists are a basic data structure that are a different approach to traditional lists and arrays. Each element in a linked list is called a node which contains the stored data as well as a pointer to the next node. This disjointed approach to lists allows for more efficient insertion and removal of elements because they do not need to be stored adjacently in memory.

Linked List vs. Array

Linked Lists	Arrays
Have a dynamic size. Not restricted by initial memory allocation.	Have a fixed size. Array must be recreated if size is exceeded.
Insertions/deletions are efficient. Simply add a node and update pointers.	Insertions/deletions are inefficient. Adjacent elements need to be shifted.
Random access is not possible without element indexes.	Random access is possible using indexes of elements.
No memory waste due to dynamic memory allocation.	Potential memory waste if an array is not full.
Sequential access is slow due to disjointed memory locations.	Sequential access is fast due to elements adjacent memory locations.

Linked List Big-O Complexity

Time Complexity

Access/Search: O(n) — Linear time. Linked list must be looped/iterated through to locate elements.

Insertion/Deletion: O(1) — Constant time. Elements can be added or removed by modifying a single node and updating pointers.

Space Complexity

All Cases: O(n) — Linear space. Linked lists contain two pieces of data for each node. As the list increases in size, so does the space used.

Linked Lists Use Cases

• Linked lists are often used for the implementation of other data types like stacks, queues, trees, and graphs.
• Real world:
• Music playlist — Each song is a node in a greater list. Songs can be easily arranged within the playlist.
• Forward/back browser buttons — Each page is a node that can be traversed to in order.
• Slideshow — Each slide is a node that can be traversed in order or rearranged.

Linked Lists Python Implementation

My full linked list Python implementation can be found on my GitHub. I’ve broken it out into the components of the data structure below.

Node Definition

A node object within a linked list has two member values. The data value stores data and the next value stores a pointer to the next node. These are None type by default. The last node in a linked list will always have a next value of None because it doesn't have a node to point to.

class Node:
    def __init__(self, data=None, next=None):
        self.data = data
        self.next = next

List Definition

The linked list object simply has to store a pointer to the first node, known as the “head” of the linked list. The following functions are also contained within the LinkedList class.

class LinkedList:
    def __init__(self):
        self.head = None

End Insert Functions

These functions add a node to the start or the end of the linked list. The insert_at_start function creates a new node and makes it the new head of the linked list. The insert_at_end function adds a head node if there are no nodes in the linked list or it iterates to the end of the linked list and adds a new node at the end.

class LinkedList:
    def insert_at_start(self, data):
        node = Node(data, self.head)
        self.head = node
    def insert_at_end(self,data):
        if self.head is None:
            self.head = Node(data, None)
            return
        itr = self.head
        while itr.next:
            itr = itr.next
        itr.next = Node(data, None)

Length Function

The get_length function simply iterates through the entire linked list and keeps a count of the length.

class LinkedList:
    def get_length(self):
        count = 0
        itr = self.head
        while itr:
            count+=1
            itr = itr.next
        return

Insert Functions

These functions insert values to the linked list. The insert_values function essentially creates a whole new linked list by setting the head to None type and then looping through provided data to form a linked list. The insert_at function inserts a value at a given index by iterating through the linked list until the next node is the desired index, then it inserts a new node. It also first does some checking to see if the desired index is out of range or is the head of the linked list.

class LinkedList:
    def insert_values(self, data_list):
        self.head = None
        for data in data_list:
            self.insert_at_end(data)
    def insert_at(self, index, data):
        if index<0 or index>=self.get_length():
            raise Exception("Not a valid index!")
        if index==0:
            self.insert_at_start(data)
        count = 0
        itr = self.head
        while itr:
            if count == index - 1:
                node = Node(data, itr.next)
                itr.next = node
                break
            itr = itr.next
            count+=1

Remove Function

The remove_at function removes a node at a given index. Much like the insert_at function it first verifies that the index is valid and if the desired index is the head of the linked list. Otherwise, the function iterates through the linked list until it is a node before the desired index and then removes the desired node by updating the pointers.

class LinkedList:
    def remove_at(self, index):
        if index<0 or index>=self.get_length():
            raise Exception("Not a valid index!")
        if index==0:
            self.head = self.head.next
            return
        count = 0
        itr = self.head
        while itr:
            if count == index - 1:
                itr.next = itr.next.next
                break
            itr = itr.next
            count+=1

By Value Functions

These functions insert or remove nodes based on value rather than index. They work much like the index-based insert and remove functions, except they do not need to count an index number and instead iterate through the linked list until a node contains matching data.

class LinkedList:
    def insert_after_value(self, after, data):
        if self.head is None:
            return
        if self.head.data == after:
            self.head.next = Node(data, self.head.next)
            return
        itr = self.head
        while itr:
            if itr.data == after:
                itr.next = Node(data, itr.next)
                break
            itr = itr.next
    def remove_by_value(self, data):
        if self.head is None:
            return
        if self.head.data == data:
            self.head = self.head.next
            return
        itr = self.head
        while itr.next:
            if itr.next.data == data:
                itr.next = itr.next.next
                break
            itr = itr.next

Print Function

The print function is a necessity for testing all of the other functions and seeing the implementation in action. This function iterates through the linked list and concatenates all nodes with a -> as a delimiter for visualizing the linked list.

class LinkedList:
    def print(self):
        if self.head is None:
            print("Linked list is empty!")
            return
        itr = self.head
        llstr = ""
        while itr:
            llstr += str(itr.data) + "->"
            itr = itr.next
        print(llstr)

Even More

• There’s also a variation of linked lists called a doubly linked list. It’s just like a linked list except it has pointers in each node going in both directions. This means that the linked list can be traversed in either direction, not just starting at the head. The Python implementation of this data structure is similar and I have it on my GitHub as well.
• Even more complex is a circular linked list. You guessed it, the entire list loops where the end node actually points to the head node. So there actually is no end or head node. This type of linked list has no null values without any ends.

That’s linked lists! Be sure to check out all of my posts about coding and other algorithms and data structures.