A linked list is a data structure which is made up of nodes connected in a chain-like manner.

Elements/nodes in a linked list are not stored in consecutive memory locations like in an array(such as python list). Instead, the elements are scattered throughout the memory and each nodes contains a pointer to the location of the next node in the list.

Node in a linked list.

There are several types of linked lists depending on the relation between the nodes. In this article we will focus on singly-linked lists. 

In a singly-linked list, each node has two parts: a value and a pointer to the next node in the list. The first node in the list is called the head, and the last node is called the tail. A null object is usually used to indicate the end of the list.

The figure below demonstrates the structure of a singly linked list.

parts of a linked list

Singly-linked lists  allow traversal only in one direction. By starting from the head and moving to the next node via the link, we can reach the end of the list. However, there is no way of  reaching the previous node and, therefore, traversal cannot happen backwards.

In most practical cases, a singly linked list is used to implement  other data structures such as stacks, queues, and trees.

Implement Stack using singly linked list

A stack is a data structure in which the last element to be inserted is also the first one to be removed. This is also known as the List-In-First-Out(LIFO) principle. A stack typically supports the following operations:

push(e) Pushes element e at the top of the stack.
pop() removes an returns the element at the top. Raises an error if the stack is empty
top() Returns the element at the top without removing it. Raises an error if the stack is empty.
is_empty() Returns True if the stack is empty, False otherwise.
len() Returns the number of elements in the stack.

In this part we will implement a stack using a singly linked list.

We will implement a non-public subclass _Node, to represent a node in the linked structure. The implementation of the _Node class is as shown below:

The _Node class 

class _Node:
    def __init__(self, e, n):
        self._element = e #Users element
        self._next = n #The next node in the list

We will use the _Node subclass for low-level operations. The final user will not interact with the class.

Implement the stack

#an exception to be raised by an empty stack
class Empty(Exception):
    pass

class Stack:
    class _Node:
        def __init__(self, e, n):
            self._element = e #Users element
            self._next = n #The next node in the list

    def __init__(self):
        self._head = None #Reference the first node in the linked list
        self._size = 0    #The number of elements in the stack

    def __len__(self):
        return self._size 

    def is_empty(self):
         return len(self) == 0

    def push(self, e):
        #add a new element to the stack
        self._head = self._Node(e, self._head)
        self._size += 1

    def top(self):
        if self.is_empty():
            raise Empty("Stack is empty.")
        return self._head._element

    def pop(self):
        if self.is_empty():
            raise Empty("Stack is empty.")

        element = self._head._element
        self._head = self._head._next # make the 
        self._size -= 1
        return element

# test the stack

S = Stack()
S.push(10)
S.push(20)
S.push(30)
S.push(40)
S.push(50)
print("Size: ", len(S))

while not S.is_empty():
    print(S.pop())

Implement Queue using singly linked list

A queue is a type of data structure that follows the First-Out-First-In(FIFO) principle. This is where elements are added at one end and removed from the other. A queue supports the following operations:

enqueue(e) Add element e at the back of the queue.
dequeue() Remove and return the element at the front of the queue. An exception is raised if empty.
first() Return the first element without removing it. An exception is raised if empty.
is_empty() Return True, if the queue is empty and False otherwise.
len() Return the number of elements in the queue.

As we saw in the previous section, operations in a stack only happens at one end and we therefore only needed to track one end using the _head variable. But in a queue, operations happen in both ends, as we are inserting in one end and removing from the other. We will, therefore, need to track the nodes at both ends.

The following snippet hows the implementation of  a Queue using singly-linked list.

Implement a Queue

#an exception to be raised by an empty Queue
class Empty(Exception):
    pass

class Queue:
    class _Node:
        def __init__(self, e, n):
            self._element = e #Users element
            self._next = n #The next node in the list

    def __init__(self):
        self._head = None #Reference the first node
        self._tail = None #refernce the last node
        self._size = 0    #The number of elements in the queue

    def __len__(self):
        return self._size 

    def is_empty(self):
         return len(self) == 0

    def first(self):
        if self.is_empty():
            raise Empty("Queue is empty.")
        return self._head._element

    def enqueue(self, e):
        #add a new element at the back
        newnode = self._Node(e, None)
        if self.is_empty():
            self._head = newnode #if the queue is empty, the newnode becomes the head
        else:
            self._tail._next = newnode  #if the queue is not empty, the last node points to the new node
        self._tail = newnode #The new node becomes the tail
        self._size += 1

    def dequeue(self):
        if self.is_empty():
            raise Empty("Queue is empty.")
        element = self._head._element
        self._head = self._head._next # Make the next node the new head
        self._size -= 1
        return element

# test the stack
Q = Queue()
Q.enqueue(100)
Q.enqueue(200)
Q.enqueue(300)
Q.enqueue(400)
Q.enqueue(500)
print("Size: ", len(Q))
print(Q.first())
while not Q.is_empty():
    print(Q.dequeue())

print("Size:", len(Q))