Linked Lists

Linked lists are a popular data structure.

The disadvantage of arrays was that continuous memory space needed to be allocated for arrays, and it might happen that there is no continuous memory block available in your memory in which case your program will not work.

This is where linked lists shine, they do not use continuous memory blocks but rather store values at different locations hence even if continuous space is not available, linked list will be present and your program will work.

Google Images: Singly and Doubly Linked Lists

But how does a linked list know where the next element is present?
Arrays had continuous memory allocation just like houses in a colony, the next house has house number one more than you so the address is obvious.

But linked lists nodes or values have different addresses.
Each node in a linked list has a pointer, generally known as the next pointer. This pointer stores the address of the next node in the list.

Each node has the following attributes:

Node:
    data
    next

The data attribute stores the value of the current whereas the next attribute is a pointer to the next node in the list.

In programming languages such as C/C++, you are allowed to play with pointers and addresses, hence you can directly store the memory addresses of the nodes using pointers. 

struct node {
  int data;
  struct node *next;
}*head = NULL;

Whereas in other programming languages use of pointers is not allowed and hence we use the object-oriented approach for constructing a node using classes.

# Node class
class Node:
    # Constructor to initialise data and next
    def __init__(self, data):
        self.data = data
        self.next = None

A node is just a part of the linked list and hence we can make a container class to store an instance of a linked list as follows:

class LinkedList:
    # Constructor to initialise head
    def __init__(self, head=None):
        self.head = head

For learning how are classes and objects used in python you can refer to this link: Object-Oriented Programming in Python Introduction

Each linked list has a special Node known as the head of the linked list. It is used to store the address of the first node of the linked list.

The last node of the list generally points to NULL which denotes the end the of the linked list.

Types of linked lists:

There are many types of linked lists, but there are mainly 3:

1. Singly Linked List:

These only have the next pointer and data attribute and hence you cannot move backwards in the list.

2. Double Linked List:

The nodes have pointers to both the next and the previous nodes. Hence backwards traversal is easy.

3. Circular Linked List:

In this type of linked list, the last node's next pointer points to the first node or the head of the linked list.

There are many advantages as well as disadvantages of linked lists over an array.

For example, There is no random access of elements in linked lists.

You'll always have to start from the first node in the list to search or get an element, whereas in the case of arrays random access was easy.

You could simply say arr[5] to access the 6th element in the array.

Also, Linked lists allow dynamic memory allocation. What this means is that we could add a new node to the list even while the program is running. This helps in adding new data at runtime which is a common use case in real world.

Operations on a linked list:

You'll mostly be asked a question on singly linked lists in interviews.

The basic operations are insertion, deletion, searching an element in the list. Which could be further categorised as:

1. Insertion at the beginning of the list

2. Insertion at the end of the list

3. Insertion in between the list

4. Deletion at the beginning of the list

5. Deletion at the end of the list

6. Deletion in between the list

Code for Operations on Singly Linked List in Python:

# class of a node
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

# class of the signly linked list
class SinglyLinkedList:
    def __init__(self):
        self.head = None
    
    # function to calculate size of the list
    def size(self):
        # initialize temporary variable and size to zero
        current = self.head
        size = 0
        
        # count until current does not reach the end of the list i.e. NULL or None
        while current is not None:
            size += 1
            current = current.next
        return size

    # function to insert at the end of the list
    def insert_at_end(self, data):
        # Create the new node
        node = Node(data)

        # If the list is empty
        if self.head is None:
            self.head = node
        else:
            current = self.head

            # Otherwise move to the last node of the list
            while current.next is not None:
                current = current.next

            # Point the last node of the list to the new node
            # So that the new node gets added to the end of the list
            current.next = node

    # function to insert at the beginning of the list
    def insert_at_beg(self, data):
        node = Node(data)
        # Next pointer of the new node points to the head
        node.next = self.head

        # Updated the head as new node
        self.head = node

    # function to delete from the end of the list
    def delete_from_end(self):
        current = self.head
        previous = None

        if current is None:
            print("Linked List Underflow!!")
        else:
            while current.next is not None:
                previous = current
                current = current.next

            if previous is None:
                self.head = None
            else:
                previous.next None

    # function to delete from the beginning of the list
    def delete_from_beg(self):
        current = self.head

        if current is None:
            print("Linked List Underflow!!")
        else:
            self.head = current.next

    # function to print the linked list data
    def print_data(self):
        current = self.head

        while current is not None:
            print(current.data, '->', end='')
            current = current.next
        print('End of list')

# Main program:

# Create a singly linked list object
linked_list = SinglyLinkedList()

# Insert at the beginning 3, 2, 1
linked_list.insert_at_beg(3)
linked_list.insert_at_beg(2)
linked_list.insert_at_beg(1)
print('After insertion at the beginning:')
linked_list.print_data()

# Insert at the end of the list 4, 5
linked_list.insert_at_end(4)
linked_list.insert_at_end(5)
print('After insertion at the end:')
linked_list.print_data()

# Delete 1 from the beginning
print('After deletion at the beginning:')
linked_list.delete_from_beg()
linked_list.print_data()

# Delete 5 from the end
print('After deletion at the end:')
linked_list.delete_from_end()
linked_list.print_data()

# print size of the list
print("size: ", linked_list.size())

"""
Outputs:
After insertion at the beginning:
1 ->2 ->3 ->End of list

After insertion at the end:
1 ->2 ->3 ->4 ->5 ->End of list

After deletion at the beginning:
2 ->3 ->4 ->5 ->End of list

After deletion at the end:
2 ->3 ->4 ->End of list

size:  3
"""

Code in C: Operations on Linked List in C

Further Reading:

1. Insertion in linked list

2. Deletion in linked list

3. Various topics on linked list

In the coming posts, we are going to see some popular interview questions on linked lists.

--
Have any questions or suggestions? Post in the comments below!!

By,
Anubhav Shrimal