Introduction to Linked List

This article highlights the difference between linked lists and other data structures. Real-life usage of linked list and how it can be implemented in different programming languages.

A linked list is a linear data structure consisting of a sequence of nodes, where each node contains a value and a reference (or pointer) to the next node in the sequence. Unlike arrays, linked lists do not require contiguous memory, which makes them more flexible for dynamic memory allocation.

There are several types of linked lists, including:

1. Singly linked lists: Each node contains a value and a reference to the next node in the sequence. The last node has a reference to null, indicating the end of the list.
2. Doubly linked lists: Each node contains a value, a reference to the next node in the sequence, and a reference to the previous node in the sequence. This allows for easier traversal in both directions.
3. Circular linked lists: Similar to singly linked lists, but the last node points to the first node, creating a circular structure.
4. Doubly circular linked lists: Similar to doubly linked lists, but the last node points to the first node, creating a circular structure.

How the linked list is better than other datatypes?

Linked lists offer a number of advantages over other data structures in certain scenarios. One of the main benefits of using a linked list is its dynamic nature, which allows for the efficient insertion and deletion of elements without requiring any restructuring of the entire list.

This makes linked lists particularly useful when dealing with large or frequently changing sets of data. Additionally, linked lists have the ability to grow or shrink as needed, providing flexibility in terms of memory allocation.

Another key advantage of linked lists is their ability to easily traverse the elements of the list in sequential order, making them well-suited for tasks such as iteration or searching.

Furthermore, linked lists can be implemented in a variety of ways, including singly linked lists, doubly linked lists, and circular linked lists, which allows for even greater flexibility in terms of how data is organized and accessed.

Overall, the benefits of linked lists make them a valuable tool for developers and programmers in a wide range of applications, particularly when dealing with complex or changing data structures.

Cons of linked list compared to Hashes and Arrays

There are several disadvantages of linked lists compared to arrays and hash tables, such as:

1. Random access: Unlike arrays, linked lists do not provide constant-time random access to elements. Accessing an element in a linked list requires traversing the list from the beginning until the desired element is found, which can be slower for large lists.
2. Memory overhead: Linked lists require more memory per element than arrays because each element in a linked list must store a reference to the next element. This additional memory overhead can become significant for large lists.
3. Inefficient traversal: Linked lists do not perform well when traversed randomly or backwards because each node only has a reference to the next node, not the previous node.
4. Hash tables are more efficient for lookup: Hash tables provide constant-time lookup for elements based on a key, while linked lists require a linear search which can be slow for large lists.

In summary, while linked lists have some advantages for certain use cases that we will discuss in next part, they can be less efficient than arrays or hash tables for other use cases due to their lack of random access, memory overhead, and inefficient traversal.

Some real-life scenarios where linked lists are used

Linked lists are utilized in a variety of real-world situations, and we’ve compiled a list of a few such examples for you to peruse.

1. Browser history: Web browsers use a linked list to keep track of the pages you’ve visited. Each page you visit is added to the beginning of the list, and the oldest page is removed when the list gets too long.
2. Music playlists: Music apps use a linked list to create playlists. Each song is represented by a node in the list, and the app plays the songs in sequence by following the references between nodes.
3. Undo/redo functionality: Some software applications use a linked list to implement undo/redo functionality. Each action the user takes is represented by a node in the list, and the application can traverse the list to undo or redo actions.
4. File systems: Some file systems use a linked list to keep track of the blocks of data on a disk. Each block is represented by a node in the list, and the file system can traverse the list to read or write data.
5. Train and bus schedules: Linked lists can be used to represent train and bus schedules, where each stop is represented as a node in the linked list, and each node contains a reference to the next stop in the sequence.
6. Sparse matrix representation: Sparse matrices with a large number of zeroes can be represented efficiently using linked lists. Each non-zero element in the matrix is represented as a node in the linked list, and each node contains a reference to the next non-zero element in the row or column.
7. LRU cache implementation: Linked lists are often used to implement the Least Recently Used (LRU) cache algorithm, which is used to cache frequently accessed data in computer systems. The cache is represented as a linked list, with the most recently accessed data at the beginning of the list and the least recently accessed data at the end.
8. Symbol table implementation: Symbol tables are used to store key-value pairs in computer science, such as in compilers and interpreters. Linked lists can be used to implement symbol tables efficiently, where each key-value pair is represented as a node in the linked list, and each node contains a reference to the next key-value pair.
9. Graph representation: Linked lists can be used to represent graphs, which are used in a wide range of applications such as social networks, road maps, and airline routes. Each vertex in the graph is represented as a node in the linked list, and each node contains a reference to the adjacent vertices.
10. Implementing stacks and queues: Linked lists can be used to implement stacks and queues, which are fundamental data structures in computer science. Each node in the linked list represents an element in the stack or queue, with the top of the stack or front of the queue at the beginning of the list.

Advantages of linked lists over other datastructure

When it comes to using linked lists, there are numerous positive aspects that one can take into account. By implementing linked lists, you can enjoy a range of benefits, some of which include:

1. Dynamic memory allocation: Linked lists can grow or shrink as needed, making them more flexible than arrays.
2. Constant-time insertion and deletion: Inserting or deleting an element in a linked list only requires updating a few references, whereas doing the same in an array may require shifting many elements.
3. Easy implementation of stacks and queues: Linked lists can be used to implement stacks and queues, which are commonly used data structures.
4. Easy insertion and deletion at the beginning of the list: Adding or removing an element at the beginning of a linked list is a constant-time operation, whereas doing the same at the beginning of an array may require shifting many elements.
5. Efficient memory utilization: Linked lists only use as much memory as needed to store the elements in the list, whereas arrays require a fixed amount of memory to be allocated regardless of how many elements are actually stored.
6. Ease of implementation: Linked lists are relatively easy to implement and manipulate compared to more complex data structures like trees and graphs.
7. Recursive data structures: Linked lists can be easily defined as recursive data structures, which makes them useful for implementing complex algorithms and data structures.
8. Flexibility in node structure: Linked lists allow for flexibility in the structure of each node, as the node can contain any combination of values and pointers to other nodes. This flexibility can be useful in a variety of applications.
9. Efficient element access: While linked lists are not as efficient as arrays for accessing elements by index, they are still relatively efficient for accessing elements by position if the position is known in advance.
10. Insertion and deletion in the middle: Linked lists can insert or delete elements at any position in the list in constant time, whereas arrays require O(n) time to shift elements after an insertion or deletion in the middle.
11. Flexibility in size and structure: Linked lists can have varying node sizes and structures, which makes them more flexible than fixed-size arrays or other data structures.
12. Concatenation and splitting: Linked lists can be easily concatenated or split into smaller lists, which can be useful in certain applications.

The following operations provide the basic functionality for manipulating a singly linked list. They can be combined and modified to solve a wide range of problems and implement various algorithms.

1. Creation
2. Insertion at beginning
3. Deletion at beginning
4. Traversal
5. Searching for a node
6. Insertion at a specific position
7. Deletion at a specific position
8. Reversing a linked list
9. Splitting a linked list
10. Joining two linked lists
11. Finding the middle node

Linked list Node Creation:

function createList():
    head = None
    return head

This function creates an empty linked list with a null head.

Node insertion at the beginning:

function insertAtBeginning(head, data):
    newNode = Node(data)
    newNode.next = head
    head = newNode
    return head

This function inserts a new node with the given data value at the beginning of the linked list. It creates a new node, sets its next pointer to the current head of the list, and updates the head to point to the new node.

Node deletion at the beginning:

function deleteAtBeginning(head):
    if head is None:
        return head
    else:
        head = head.next
        return head

This function deletes the first node in the linked list. It checks if the list is empty, and if not, it updates the head to point to the next node in the list.

Linked list Traversal:

function traverse(head):
    if head is None:
        return
    else:
        current = head
        while current is not None:
            print(current.data)
            current = current.next

This function traverses the linked list and prints the data value in each node. It starts at the head of the list, iterates through each node using the next pointers, and prints the data value of each node.

Searching for a node:

function search(head, key):
    if head is None:
        return None
    else:
        current = head
        while current is not None:
            if current.data == key:
                return current
            current = current.next
        return None

This function searches for a node with the given data value in the linked list. It starts at the head of the list, iterates through each node using the next pointers, and checks if the data value matches the key. If a match is found, it returns the node; otherwise, it returns None.

Insertion at a specific position:

function insertAtPosition(head, data, position):
    newNode = Node(data)
    if position == 1:
        newNode.next = head
        head = newNode
    else:
        current = head
        prev = None
        for i in range(1, position):
            prev = current
            current = current.next
        prev.next = newNode
        newNode.next = current
    return head

This function inserts a new node with the given data value at a specific position in the linked list. It creates a new node, and then iterates through the list to find the node at the specified position. It updates the next pointers of the nodes before and after the new node to include the new node.

Deletion at a specific position:

function deleteAtPosition(head, position):
    if head is None:
        return head
    elif position == 1:
        head = head.next
    else:
        current = head
        prev = None
        for i in range(1, position):
            prev = current
            current = current.next
        prev.next = current.next
    return head

This function deletes the node at a specific position in the linked list. It checks if the list is empty or if the position is the first node. If neither condition is true, it iterates through the list to find the node at the specified position and updates the next pointer of the node before it to point to the node after it.

Reversing a linked list:

function reverseList(head):
    if head is None or head.next is None:
        return head
    else:
        prev = None
        current = head
        while current is not None:
            nextNode = current.next
            current.next = prev
            prev = current
            current = nextNode
        head = prev
        return head

This function reverses the order of nodes in the linked list. It creates two pointers, one for the current node and one for the previous node, and iterates through the list, reversing the next pointers of each node as it goes. It also updates the head of the list to point to the last node, which becomes the new head.

Splitting a linked list:

function splitList(head, position):
    if head is None:
        return None, None
    elif position == 1:
        return head, None
    else:
        current = head
        prev = None
        for i in range(1, position):
            prev = current
            current = current.next
        prev.next = None
        return head, current

This function splits the linked list into two separate lists at a specific node position. It iterates through the list to find the node at the specified position, updates the next pointer of the node before it to null to split the list, and returns the two separate lists as separate heads.

Joining two linked lists:

function joinLists(head1, head2):
    if head1 is None:
        return head2
    elif head2 is None:
        return head1
    else:
        current = head1
        while current.next is not None:
            current = current.next
        current.next = head2
        return head1

This function joins two linked lists into a single linked list. It finds the last node of the first list using iteration and updates its next pointer to point to the head of the second list, effectively joining the two lists.

Finding the middle node:

function findMiddleNode(head):
    if head is None:
        return None
    slow = head
    fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
    return slow

This function finds the middle node of the linked list. It uses the Floyd’s algorithm to traverse the linked list with two pointers, one that moves one node at a time (slow) and another that moves two nodes at a time (fast). When the fast pointer reaches the end of the list, the slow pointer will be at the middle node.