Understanding Linked Lists

Introduction

Fundamental data structures used in computer science and programming include linked lists. They offer a dynamic method of manipulating and storing data, enabling effective insertion and deletion operations. In this article, we'll look at how a linked list is implemented, including how to add items, show them, delete them, add items at the beginning, and determine whether the list is empty. We will also go over the time-related challenges of each procedure. We will provide real-world examples that demonstrate linked lists in action to help with comprehension.

Understanding Linked Lists

A linked list is a linear data structure consisting of a sequence of nodes. Each node contains data and a reference (or link) to the next node in the list. The last node typically points to null, indicating the end of the list. Unlike arrays, linked lists do not require contiguous memory allocation, making them flexible for dynamically changing data.

There are different types of linked lists, including singly linked lists, doubly linked lists, and circular linked lists.

• In a singly linked list, each node contains a reference only to the next node.

• In a doubly linked list, each node has references to both the next and previous nodes, enabling traversal in both directions.

• A circular linked list forms a loop where the last node points back to the first node, creating a circular structure.

Node Structure

To implement a linked list, we start by defining a node structure. Each node contains two components

• The data

• The next pointer. The next pointer points to the next node in the list

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

Creating a Linked List

We must initialise the head (or start) pointer, which points to the list's very first node, to establish a linked list. The head pointer is first set to null since the list is empty. Let's examine the process for adding elements to a linked list.

• Insertion at the Beginning

  To insert an element at the beginning of the list, we create a new node and make it the head node by updating the head pointer. The next pointer of the new node will point to the previous head node.

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

• Insertion / Insertion at the End

  We navigate the list until we find the final node, and then we place an element there. Next, we build a new node and change the last node's next pointer to point at the new node.

    def insert_at_end(head, data):
        new_node = Node(data)
        if head is None:
            head = new_node
        else:
            current = head
            while current.next:
                current = current.next
            current.next = new_node
        return head
  

• Deletion

  To remove a node from a linked list, we must modify the previous node's next reference so that it skips the node that will be removed. The memory is then released from the removed node. How to remove a node with a certain data value is shown below.

    def delete_node(head, data):
        if head is None:
            return head
  
        if head.data == data:
            head = head.next
            return head
  
        current = head
        while current.next:
            if current.next.data == data:
                current.next = current.next.next
                break
            current = current.next
  
        return head
  

• Display

  To display the elements of a linked list, we traverse the list and print the data of each node.

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

• Checking if the List is Empty

  To determine whether a linked list is empty, we check if the head pointer is null. If the head is null, the list is empty.

    def is_empty(head):
        return head is None
  

Time Complexities

• Insertion at the Beginning: O(1)

• Insertion at the End: O(n)

• Deletion: O(n)

• Displaying the List: O(n)

• Checking if the List is Empty: O(1)

Real-time Example: To-Do List

Let's look at a practical example of how to develop a linked list to build a straightforward to-do list application. Users of the application can add tasks, mark them as finished, and view the list of tasks.

Implementation

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


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

    def add_task(self, task):
        new_node = Node(task)
        if self.head is None:
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node

    def mark_as_completed(self, task):
        current = self.head
        while current:
            if current.data == task:
                current.data = f"{task} (Completed)"
                break
            current = current.next

    def display_tasks(self):
        current = self.head
        if current is None:
            print("No tasks in the list.")
        else:
            print("Tasks:")
            while current:
                print(current.data)
                current = current.next

Usage/Console

# Create an instance of the ToDoList
my_todo_list = ToDoList()

# Add tasks to the list
my_todo_list.add_task("Buy groceries")
my_todo_list.add_task("Finish report")
my_todo_list.add_task("Go for a run")

# Display the tasks
my_todo_list.display_tasks()
# Output:
# Tasks:
# Buy groceries
# Finish report
# Go for a run

# Mark a task as completed
my_todo_list.mark_as_completed("Finish report")

# Display the tasks after marking one as completed
my_todo_list.display_tasks()
# Output:
# Tasks:
# Buy groceries
# Finish report (Completed)
# Go for a run

In this example, a linked list has been used to implement a ToDoList class. Each task is represented by a node in the linked list, and the node's data property contains the task description. The ToDoList class's head attribute points to the list's root node.

A new task is added to the end of the linked list using the add_task method. A specific task is sought by the mark_as_completed method, which then modifies the task's description to reflect completion. The linked list is iterated by the display_tasks method, which writes out a description for each task.

This implementation allows users to maintain and manage their to-do lists dynamically. The flexibility of linked lists enables efficient insertion and deletion of tasks, making it suitable for scenarios where the task order changes frequently or new tasks are added dynamically.

Conclusion

Linked lists are adaptable data structures that facilitate quick insertion and removal. They offer flexibility in the administration of dynamic data. In this post, we looked at how linked lists are implemented, including how they are added to, removed from, shown, and checked to see if they are empty. We also talked about how time-consuming they were, and we gave a real-world scenario to show how they may be used. You may improve your programming abilities and efficiently manage data in a variety of situations by knowing linked lists.

• Link-I, Link-II to the problems based on Linked-List.