Linked List

Memory space is a common resource for all programs. In a complex system operating environment, free memory space may be scattered throughout the memory. We know that the memory space for storing arrays must be continuous, and when the array is very large, the memory may not be able to provide such a large continuous space. At this time, the flexibility advantage of the linked list is reflected.

A linked list is a linear data structure in which each element is a node object, and each node is connected through "references". The reference records the memory address of the next node through which the next node can be accessed from the current node.

The design of the linked list allows each node to be stored scattered throughout the memory, and their memory addresses do not need to be consecutive.

Each node contains two pieces of data: the node's "value" and a "reference" to the next node.

• The first node of the linked list is called the "head node" and the last node is called the "tail node".
• null The tail node points to "null", which is recorded as, nullptr and in Java, C++, and Python respectively None.
• In languages ​​that support pointers, such as C, C++, Go, and Rust, the above "reference" should be replaced by "pointer".

As shown in the following code, ListNode in addition to containing the value, the linked list node also needs to save an additional reference (pointer). Therefore, for the same amount of data, a linked list takes up more memory space than an array.

class ListNode:
    def __init__(self, val: int):
        self.val: int = val
        self.next: ListNode | None = None

Example in real-life scenario

Suppose you are working on a project where you need to keep track of a large number of tasks that need to be completed. You could use a linked list to store the tasks, where each task is represented by a node in the list.

Each node in the list would contain information about the task, such as its description, deadline, and priority. You could also include links to other tasks that depend on the current task, or that the current task depends on.

When a new task is added to the list, a new node is created and added to the end of the list. When a task is completed, its node is removed from the list.

You could also use the linked list to keep track of the dependencies between tasks. For example, if Task A depends on Task B being completed first, you could create a link from Task A's node to Task B's node. This would allow you to easily identify which tasks need to be completed before others.

Using a linked list in this way would allow you to efficiently add, remove, and manipulate tasks in your project management system. It would also allow you to easily visualize the dependencies between tasks, which could help you identify potential bottlenecks and plan your workflow more effectively.

Here's an example of how the linked list could be implemented in Python:

class Task:
    def __init__(self, description, deadline, priority):
        self.description = description
        self.deadline = deadline
        self.priority = priority
        self.dependencies = []

    def add_dependency(self, dependency):
        self.dependencies.append(dependency)

    def remove_dependency(self, dependency):
        self.dependencies.remove(dependency)

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

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

    def remove_task(self, task):
        if self.head is None:
            return
        elif self.head == task:
            self.head = self.head.next
        else:
            current = self.head
            while current.next is not None:
                if current.next == task:
                    current.next = current.next.next
                    break
                current = current.next

    def get_tasks(self):
        tasks = []
        current = self.head
        while current is not None:
            tasks.append(current)
            current = current.next
        return tasks

# Example usage:
task1 = Task("Task 1", "2023-02-28", 1)
task2 = Task("Task 2", "2023-03-14", 2)
task3 = Task("Task 3", "2023-03-21", 3)

task1.add_dependency(task2)
task2.add_dependency(task3)

task_list = TaskList()
task_list.add_task(task1)
task_list.add_task(task2)
task_list.add_task(task3)

print(task_list.get_tasks())
# Output: [<Task 1>, <Task 2>, <Task 3>]

task_list.remove_task(task2)

print(task_list.get_tasks())
# Output: [<Task 1>, <Task 3>]