The Project | About Us | Contribute | Donations | License
HOME My courses Completed
◄ Previous
◄

Linked Lists

Next ►
►

Introduction to Linked Lists

A linked list is a linear data structure where elements are not stored in contiguous memory locations. Instead, each element, called a node, contains a data part and a reference (or link) to the next node in the sequence. This structure allows for efficient insertion and deletion of elements.

Key Concepts

  • Node: The basic unit of a linked list, containing data and a reference to the next node.
  • Head: The first node in the linked list.
  • Tail: The last node in the linked list, which points to null (or None in Python).

Advantages of Linked Lists

  • Dynamic Size: The size of a linked list can grow or shrink dynamically.
  • Efficient Insertions/Deletions: Insertions and deletions are more efficient compared to arrays, especially when dealing with large datasets.

Disadvantages of Linked Lists

  • Memory Usage: Linked lists use more memory due to the storage of references.
  • Access Time: Accessing an element by index requires traversing the list, leading to O(n) time complexity.

Structure of a Node

Here is a basic structure of a node in a linked list:

class Node:
    def __init__(self, data):
        self.data = data  # Store the data
        self.next = None  # Reference to the next node

Creating a Linked List

To create a linked list, we need to manage the head of the list and provide methods to insert, delete, and traverse the list.

Example: Singly Linked List

class LinkedList:
    def __init__(self):
        self.head = None  # Initialize the head of the list

    def insert_at_beginning(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

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

    def delete_node(self, key):
        temp = self.head

        if temp is not None:
            if temp.data == key:
                self.head = temp.next
                temp = None
                return

        while temp is not None:
            if temp.data == key:
                break
            prev = temp
            temp = temp.next

        if temp == None:
            return

        prev.next = temp.next
        temp = None

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

Explanation

  • Insert at Beginning: Adds a new node at the start of the list.
  • Insert at End: Adds a new node at the end of the list.
  • Delete Node: Removes a node with a specific value.
  • Traverse: Prints all the nodes in the list.

Practical Example

# Create a linked list and perform operations
ll = LinkedList()
ll.insert_at_end(1)
ll.insert_at_end(2)
ll.insert_at_end(3)
ll.insert_at_beginning(0)
ll.traverse()  # Output: 0 -> 1 -> 2 -> 3 -> None

ll.delete_node(2)
ll.traverse()  # Output: 0 -> 1 -> 3 -> None

Exercises with Linked Lists

Exercise 1: Insert a Node at a Specific Position

Write a method to insert a node at a specific position in the linked list.

def insert_at_position(self, data, position):
    new_node = Node(data)
    if position == 0:
        new_node.next = self.head
        self.head = new_node
        return
    current = self.head
    for _ in range(position - 1):
        if current is None:
            raise IndexError("Position out of bounds")
        current = current.next
    new_node.next = current.next
    current.next = new_node

Solution

ll = LinkedList()
ll.insert_at_end(1)
ll.insert_at_end(2)
ll.insert_at_end(4)
ll.insert_at_position(3, 2)
ll.traverse()  # Output: 1 -> 2 -> 3 -> 4 -> None

Exercise 2: Reverse a Linked List

Write a method to reverse the linked list.

def reverse(self):
    prev = None
    current = self.head
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    self.head = prev

Solution

ll = LinkedList()
ll.insert_at_end(1)
ll.insert_at_end(2)
ll.insert_at_end(3)
ll.insert_at_end(4)
ll.reverse()
ll.traverse()  # Output: 4 -> 3 -> 2 -> 1 -> None

Common Mistakes and Tips

  • Null References: Always check for None references to avoid null pointer exceptions.
  • Boundary Conditions: Handle edge cases such as inserting or deleting nodes at the beginning or end of the list.
  • Memory Management: Ensure that deleted nodes are properly de-referenced to avoid memory leaks.

Conclusion

In this section, we covered the basics of linked lists, including their structure, advantages, and disadvantages. We also implemented a simple singly linked list with basic operations and provided exercises to reinforce the concepts. Understanding linked lists is fundamental for mastering more complex data structures and algorithms.

◄ Previous
◄
Next ►
►
The Project | About Us | Contribute | Donations | License
© Copyright 2024. All rights reserved