Data Structure & Algorithm Takeaway: Linked List

TipWhat is a linked list?

Linked list is representation of a linear list in which elements are stored in non-contiguous memory locations. Each element can be accessed indirectly using pointers.

TipHow to store a linked list in computer memory?

A linked list is stored in non-contiguous memory locations. Each element in a linked list is called a node, and each node contains two parts: the data part, which stores the actual value of the element, and the pointer part, which stores the address of the next node in the list. The first node in the list is called the head, and the last node points to null, indicating the end of the list.

Linked list in memory. (Source: GeeksForGeeks)

WarningIs there any other way to link the nodes?

The nodes are linked in one way in the above linked list, which is callout singly linked list. However, there are several variants of linked list that link the nodes in different ways.

• Doubly linked list: Each node contains a pointer to both the next and the previous node in the list. This allows for more efficient traversal in both directions, but requires more memory for the additional pointer.
• Circular linked list: The last node in the list points back to the head node, forming a circular structure. This allows for continuous traversal of the list without reaching the end.

TipIs there any requirement for the element? Why?

All elements in a linked list can be of different data types, because each node contains a pointer to the next node, allowing for a flexible structure.

ImportantWhat are the time complexities of operations in a linked list?

The time complexities of common operations in an array are as follows ($n$ is the number of elements in the linked list):

• Structural operations:
  • Initialise a linked list with initial values: $O(1)$;
  • Destroy a linked list: $O(n)$;
  • Clear a linked list: $O(n)$;
  • Check if the linked list is empty: $O(1)$;
  • Get the length of the linked list: $O(n)$.
• Element access operations:
  • Get an element by its index: $O(n)$;
  • Search for an element by its value: $O(n)$;
  • Traverse all elements with a specific operation on each element (such as printing): $O(n)$.
• Element modification operations:
  • Update the value of an element by its index: $O(n)$;
  • Insert a new element at a specific index: $O(n)$;
    • Append an element to the end of the list: $O(n)$;
    • Prepend an element to the beginning of the list: $O(1)$;
  • Delete an element from a specific index: $O(n)$;
    • Delete the last element of the list: $O(n)$;
    • Delete the first element of the list: $O(1)$.
• Sorting the elements: $O(n\log n)$ on average for efficient algorithms like mergesort; $O(n^2)$ for simpler algorithms like bubble sort and insertion sort.

ImportantWhy is the time complexity $O(n)$ for access, update, insert and delete operation?

Since linked lists are stored in non-contiguous memory locations, we cannot directly access an element by its index. Instead, we need to traverse the list from the head node to the desired index, which takes linear time in the worst case, resulting in a time complexity of $O(n)$ for access, update, insert and delete operations.

TipWhat are the pros and cons of linked list?

Pros:

• Dynamic size: Linked lists can grow and shrink in size as needed, while arrays have a fixed size.
• Memory efficiency: Linked lists can be more memory efficient than arrays when the number of elements is not known in advance, as they do not require pre-allocation of memory.

Cons:

• Slower access time: Accessing an element in a linked list takes linear time in the worst case, while accessing an element in an array takes constant time.
• More memory overhead: Each node in a linked list requires additional memory for storing the pointer to the next node, which can lead to increased memory usage compared to arrays.

WarningHow to implement a linked list in C and C++?

C and C++ do not have a built-in linked list data type, but a linked list can be implemented using structures and pointers.

#include <stdio.h>
#include <stdlib.h> 

// Define the structure for a node in the linked list
struct Node {
    int data;
    struct Node* next;
};

WarningHow to implement a linked list in Python?

Python does not have a built-in linked list data type, but a linked list can be implemented using classes and references.

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

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

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node

    def print_list(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")