Boost Coding Skills :Linked Lists Data Structures and Algorithms 🚀

Java Project Java Notes Updategadh September 20, 2023

Linked Lists Data Structures

Linked Lists Data Structures are fundamental data structures in computer science used to store and manipulate collections of data. They consist of nodes, where each node contains data and a reference (or pointer) to the next node in the sequence. There are several types of linked lists, including singly linked lists, doubly linked lists, and circular linked lists, each with its own characteristics and use cases. Let’s explore these concepts in more detail:

Singly Linked List:

In a singly linked list, each node points to the next node in the list, forming a unidirectional chain.
The last node typically points to null to indicate the end of the list
Common operations:
- Insertion: To add a new node, you update the next pointer of the previous node to point to the new node.
- Deletion: To remove a node, you update the next pointer of the previous node to skip the node to be deleted.

Doubly Linked List:

In a doubly linked list, each node has pointers to both the next and the previous nodes, allowing bidirectional traversal.
It’s useful for operations that require both forward and backward traversal.
Common operations:
- Insertion: To add a new node, you update the next and previous pointers of neighboring nodes.
- Deletion: To remove a node, you update the next and previous pointers of neighboring nodes to bypass the node to be deleted.

Circular Linked List:

In a circular linked list, the last node’s next pointer points back to the first node, forming a closed loop.
It’s often used in applications where you need to traverse a list indefinitely.
Common operations are similar to those in singly or doubly linked lists.

Source Code

Singly Linked List Source Code:

Here’s an example of how to traverse a singly linked list in Python:

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
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node

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

# Example usage:
llist = LinkedList()
llist.append(1)
llist.append(2)
llist.append(3)
llist.display()

Certainly! Here are code examples for each type of linked list: singly linked list, doubly linked list, and circular linked list in Python:

Singly Linked List:

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

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

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

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

# Example usage:
sll = SinglyLinkedList()
sll.append(1)
sll.append(2)
sll.append(3)
sll.display()

Doubly Linked List Source Code:

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

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

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node
            new_node.prev = current

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

# Example usage:
dll = DoublyLinkedList()
dll.append(1)
dll.append(2)
dll.append(3)
dll.display()

Circular Linked List Source Code:

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

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

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            self.head.next = self.head  # Circular reference to itself
        else:
            current = self.head
            while current.next != self.head:
                current = current.next
            current.next = new_node
            new_node.next = self.head

    def display(self):
        current = self.head
        if not current:
            print("List is empty.")
            return
        while True:
            print(current.data, end=" -> ")
            current = current.next
            if current == self.head:
                break
        print()

# Example usage:
cll = CircularLinkedList()
cll.append(1)
cll.append(2)
cll.append(3)
cll.display()

These code examples provide a basic implementation of each type of linked list with append and display functions for demonstration purposes. You can extend them to include other operations like deletion, searching, and more as needed.