Single Linked Lists: Building Blocks of Data Structures

Data structures are fundamental building blocks in computer science, and one such essential structure is the single linked list. Single linked lists provide a green manner to shop and manipulate data dynamically. On this weblog, we’re going to find out the idea of single related lists, their advantages and packages, and a manner to implement and manipulate them in numerous programming languages.

Table of Contents

• What is a Single Linked List?
• Advantages of Single Linked Lists
• Common Operations on Single Linked Lists
• Code
• Conclusion

What is a Single Linked List?

A single linked list is a linear data structure that consists of a sequence of nodes, where each node contains data and a reference (or link) to the next node in the list. The last node points to NULL, indicating the end of the list. Unlike arrays, linked lists do not require contiguous memory allocation, making them flexible and adaptable to dynamic data storage needs.

Advantages of Single Linked Lists

• Dynamic Size: Linked lists can grow or shrink dynamically, as nodes can be easily added or removed without requiring memory reallocation or resizing.
• Efficient Insertion and Deletion: Insertion or deletion of nodes in a linked list can be done in constant time (O(1)) by adjusting the references, as opposed to arrays where such operations may involve shifting elements, resulting in linear time (O(n)) complexity.
• Flexible Memory Allocation: Linked lists can efficiently utilize memory by allocating space for each node as needed, unlike arrays, which require pre-allocation of memory.
• Easy Implementation: Linked lists are relatively easy to implement and manipulate, making them suitable for a wide range of applications.

Common Operations on Single Linked Lists

Single linked lists are a fundamental data structure in computer science. They include nodes, in which every node carries data and a reference (or pointer) to the following node within the listing. Right here are some not unusual operations finished on single connected lists:

1. Insertion at the start: This operation entails including a new node at the beginning of the connected listing. The brand new node will become the new head of the list.
2. Insertion at the stop: in this operation, a brand new node is introduced at the cease of the connected listing. The new node turns into the final node within the list.
3. Insertion at a selected position: a new node may be inserted at a selected position in the connected listing. This includes adjusting the suggestions of the previous and subsequent nodes to include the brand new node.
4. Deletion from the beginning: This operation gets rid of the primary node (head) from the connected listing and updates the pinnacle pointer to factor to the next node.
5. Deletion from the stop: The closing node of the connected list is eliminated in this operation, and the second one-to-closing node’s pointer is up to date to factor to null.
6. Deletion of a particular Node: A node at a selected position is removed, and the recommendations of the previous and subsequent nodes are adjusted to pass the removed node.
7. Traversal: Traversing a related listing involves touring every node one after the other, beginning from the head, and doing some operation on the node’s facts.
8. Looking: trying to find a selected cost in a related listing involves traversing the listing until the favored price is discovered or till the stop of the list is reached.
9. Finding the length: The period of the connected listing (variety of nodes) may be decided by using traversing the list and counting the nodes.
10. Reversing the list: Reversing the connected list involves changing the direction of pointers so that the ultimate node becomes the brand new head and the vintage head turns into the brand new tail.
11. Merging Lists: Combining two linked lists into a unmarried list may be finished by using adjusting tips correctly.
12. Detecting a Cycle: If a linked list has a cycle (a loop), algorithms can be implemented to stumble on the presence of the cycle and discover the start line of the cycle.
13. Eliminating Duplicates: disposing of replica nodes (nodes with the equal statistics) from a linked listing entails traversing the list and adjusting tips to eliminate duplicates.
14. Locating the Nth Node from the stop: This operation entails finding the Nth node from the stop of the related list. It may be carried out the usage of tips with a particular distance between them.
15. Splitting the list: Splitting a connected list into two lists may be finished based on a positive situation or role.

Those are just some of the not unusual operations completed on single linked lists. Each operation requires careful manipulation of pointers to maintain the integrity of the list shape. It’s important to handle edge cases and take into account the complexity of those operations for green implementations.

Code

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


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

    def __iter__(self) -> Any:
       
        node = self.head
        while node:
            yield node.data
            node = node.next

    def __len__(self) -> int:
        
        return len(tuple(iter(self)))

    def __repr__(self) -> str:
       
        return "->".join([str(i) for i in self])

    def __getitem__(self, index: int) -> Any:
        
        if not 0 <= index < len(self):
            raise ValueError("list index out of range.")
        for i, node in enumerate(self):
            if i == index:
                return node

    def __setitem__(self, index: int, data: Any) -> None:
        if not 0 <= index < len(self):
            raise ValueError("list index out of range.")
        current = self.head
        for _ in range(index):
            current = current.next
        current.data = data

    def insert_tail(self, data: Any) -> None:
        
        self.insert_nth(len(self), data)

    def insert_head(self, data: Any) -> None:

        self.insert_nth(0, data)

    def insert_nth(self, index: int, data: Any) -> None:

        if not 0 <= index <= len(self):
            raise IndexError("list index out of range")
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
        elif index == 0:
            new_node.next = self.head 
            self.head = new_node
        else:
            temp = self.head
            for _ in range(index - 1):
                temp = temp.next
            new_node.next = temp.next
            temp.next = new_node

    def print_list(self) -> None:  

        print(self)

    def delete_head(self) -> Any:

        return self.delete_nth(0)

    def delete_tail(self) -> Any:  

        return self.delete_nth(len(self) - 1)

    def delete_nth(self, index: int = 0) -> Any:

        if not 0 <= index <= len(self) - 1:  
            raise IndexError("List index out of range.")
        delete_node = self.head  
        if index == 0:
            self.head = self.head.next
        else:
            temp = self.head
            for _ in range(index - 1):
                temp = temp.next
            delete_node = temp.next
            temp.next = temp.next.next
        return delete_node.data

    def is_empty(self) -> bool:

        return self.head is None

    def reverse(self) -> None:

        prev = None
        current = self.head

        while current:
            next_node = current.next
            current.next = prev
            prev = current
            current = next_node
        self.head = prev


if __name__ == "__main__":

    linked_list = LinkedList()
    linked_list.insert_head(input("Enter Value = "))
    linked_list.insert_head(input("Enter Value = "))
    linked_list.print_list()
    linked_list.insert_tail(input("\nEnter Value =  "))
    linked_list.print_list()
    print("\nDelete head")
    linked_list.delete_head()
    linked_list.print_list()
    print("\nReverse linked list")
    linked_list.reverse()
    linked_list.print_list()
    print("\nString representation of linked list:")
    print(linked_list)

Conclusion

Single-linked lists are versatile records structures that provide flexibility and efficient reminiscence usage. They are generally utilized in various programs, such as enforcing stacks, queues, and graphs, and are crucial for dynamic information control. Know-how the concepts and operations of single related lists is vital for every programmer. Optimistically, this blog post has provided a stable introduction to single-connected lists and their implementation in Python. With this knowledge, you can confidently leverage related lists to remedy a wide variety of programming problems.