Introduction to Linked Lists

Welcome to the world of Linked Lists! In this lesson, we will dive into the concept of linked lists and explore their basic properties.

As a medium-level programmer in Python and C++, you may already be familiar with data structures like arrays. Linked lists provide an alternative way to store and manipulate data.

A linked list is a linear data structure consisting of a series of nodes. Each node contains a value, and a reference to the next node in the list. Unlike arrays, linked lists do not require contiguous memory and can dynamically grow or shrink as elements are added or removed.

To help you grasp the concept, let's take a basketball analogy. Imagine a team huddle, where each player holds hands with the player next to them. The player at the front is the head of the list, and the player at the back is the tail. Each player is a node, with their jersey number representing the value. The hand-holding represents the references, connecting the players together.

1class Node:
2    def __init__(self, value):
3        self.value = value
4        self.next = None
5
6# Creating nodes
7player1 = Node(24)
8player2 = Node(8)
9player3 = Node(23)
10
11# Linking the nodes
12player1.next = player2
13player2.next = player3

Singly Linked List

A singly linked list is a linear data structure consisting of a sequence of nodes, where each node stores a data element and a reference (link) to the next node in the list. The first node is called the head, and the last node's reference points to null, indicating the end of the list.

Implementation

To implement a singly linked list, we can define two classes: Node and SinglyLinkedList.

The Node class represents each individual node in the list. It has two properties: data to store the actual data, and next to store the reference to the next node.

The SinglyLinkedList class represents the entire linked list. It has one property: head to store the reference to the first node in the list. It also has methods to insert elements at the end of the list (insert_at_end) and display the list (display).

Here is an example of a singly linked list implementation in Python:

1# Singly Linked List Implementation in Python
2
3class Node:
4    def __init__(self, data):
5        self.data = data
6        self.next = None
7
8
9class SinglyLinkedList:
10    def __init__(self):
11        self.head = None
12
13    def insert_at_end(self, data):
14        new_node = Node(data)
15        if self.head is None:
16            self.head = new_node
17        else:
18            current = self.head
19            while current.next:
20                current = current.next
21            current.next = new_node
22
23    def display(self):
24        if self.head is None:
25            print('The list is empty')
26        else:
27            current = self.head
28            while current is not None:
29                print(current.data, '->', end=' ') if current.next else print(current.data)
30                current = current.next
31
32
33# Create a singly linked list
34linked_list = SinglyLinkedList()
35
36# Insert elements
37linked_list.insert_at_end(10)
38linked_list.insert_at_end(20)
39linked_list.insert_at_end(30)
40
41# Display the linked list
42linked_list.display()

Remember to always ensure that the next of the last node is None to indicate the end of the list.

xxxxxxxxxx

linked_list.display()

# Singly Linked List Implementation in Python

​

class Node:

    def __init__(self, data):

        self.data = data

        self.next = None

​

​

class SinglyLinkedList:

    def __init__(self):

        self.head = None

​

    def insert_at_end(self, data):

        new_node = Node(data)

        if self.head is None:

            self.head = new_node

        else:

            current = self.head

            while current.next:

                current = current.next

            current.next = new_node

​

    def display(self):

        if self.head is None:

            print('The list is empty')

        else:

            current = self.head

            while current is not None:

                print(current.data, '->', end=' ') if current.next else print(current.data)

Doubly Linked List

A doubly linked list is a variation of a linked list in which each node has a reference to both the previous node and the next node. This bidirectional linkage allows for efficient traversal in both directions.

Advantages over Singly Linked List

The main advantage of a doubly linked list over a singly linked list is the ability to traverse the list in both directions. This is useful in many scenarios, especially when you need to access elements in reverse order or when you need to perform operations that require backtracking.

Implementation

To implement a doubly linked list, we can define two classes: Node and DoublyLinkedList.

The Node class represents each individual node in the list. It has three properties: data to store the actual data, prev to store the reference to the previous node, and next to store the reference to the next node.

The DoublyLinkedList class represents the entire linked list. It has one property: head to store the reference to the first node in the list. It also has methods to append elements at the end of the list (append) and display the list (display).

Here is an example of a doubly linked list implementation in Python:

xxxxxxxxxx

linked_list.display()

## Doubly Linked List

​

class Node:

    def __init__(self, data):

        self.data = data

        self.prev = None

        self.next = 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)

            current = current.next

Circular Linked List

A circular linked list is a variation of a linked list in which the last node's next pointer points back to the first node, forming a loop. This creates a circular structure that allows for continuous traversal of the list.

Applications

Circular linked lists have various applications in robotics and computer vision due to their cyclic nature. Some common applications include:

• Task Scheduling: Circular linked lists can be utilized in scheduling algorithms to assign and manage tasks in a cyclic manner.

• Sensor Data Collection: In robotics and computer vision, circular linked lists can be used to continuously collect and process data from sensors in a circular fashion.

• Buffer Management: Circular linked lists are commonly used in buffer management systems where data needs to be stored and processed in a circular order.

xxxxxxxxxx

cll.display()

# Circular Linked List Implementation in Python

​

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 self.head is None:

            self.head = new_node

            new_node.next = self.head

        else:

            temp = self.head

            while temp.next != self.head:

                temp = temp.next

            temp.next = new_node

            new_node.next = self.head

​

    def display(self):

        if self.head is None:

            print('Circular Linked List is empty')

        else:

            temp = self.head

            while True:

Operations on Linked Lists

Linked lists support various operations, including insertion, deletion, and traversal. Let's take a look at each of these operations in detail.

Insertion

Insertion refers to adding an element to a linked list. There are several scenarios to consider when inserting an element:

• Insertion at the beginning: In this case, a new node is created and its next pointer is set to the current head of the linked list. The new node then becomes the new head.

• Insertion at the end: When inserting at the end, a new node is created and its next pointer is set to None. The next pointer of the last node in the linked list is then updated to point to the new node.

• Insertion at a specific position: To insert an element at a specific position, we first need to traverse the linked list to find the position where we want to insert the new node. We then update the next pointers of the nodes before and after the position to include the new node.

Here's the Python code for the insertion operation:

{{code}}

Deletion

Deletion involves removing an element from the linked list. Similar to insertion, there are several scenarios to consider:

• Deletion of the head node: In this case, we simply update the head pointer to point to the next node in the list

• Deletion of a node: To delete a non-head node, we need to find the node and update the next pointer of the previous node to skip the node to be deleted.

Here's the Python code for the deletion operation:

{{code}}

Traversal

Traversal involves visiting each element in the linked list and performing some operation on it. In this case, we simply print the data of each node in the linked list.

Here's the Python code for the traversal operation:

{{code}}

xxxxxxxxxx

llist.traverse()

# Python code for Linked List operations

​

# Node class

class Node:

    def __init__(self, data=None):

        self.data = data

        self.next = None

​

# LinkedList class

class LinkedList:

    def __init__(self):

        self.head = None

​

    # Insertion operation

    def insert(self, data):

        new_node = Node(data)

        if self.head is None:

            self.head = new_node

        else:

            temp = self.head

            while temp.next:

                temp = temp.next

​

    # Deletion operation

    def delete(self, data):

        if self.head is None:

            return None

        temp = self.head

        if temp.data == data:

Time and Space Complexity

When analyzing the time and space complexity of linked list operations, it is important to consider the specific operation being performed.

• Insertion:

  • Insertion at the beginning of a linked list takes constant time (O(1)) since it only requires updating the head pointer.
  • Insertion at the end of a linked list takes linear time (O(n)) as we need to traverse the entire list to find the last node.
  • Insertion at a specific position also requires traversing the list, resulting in a time complexity of O(n).

• Deletion:

  • Deletion of the head node takes constant time (O(1)) as we only need to update the head pointer.
  • Deletion of a non-head node requires traversing the list to find the node and updating the previous node's pointer. This operation also has a time complexity of O(n).

• Traversal: Traversing a linked list to visit each node and perform some operation takes linear time (O(n)) as we need to visit each node once.

When it comes to space complexity, linked lists require additional memory to store the nodes and their pointers.

• Singly Linked List: In a singly linked list, each node contains a reference to the next node, resulting in a space complexity of O(n).

• Doubly Linked List: Doubly linked lists, in addition to the next pointer, also contain a previous pointer, doubling the storage requirement. Therefore, the space complexity of a doubly linked list is also O(n).

• Circular Linked List: Like a singly linked list, a circular linked list has a space complexity of O(n) due to the next pointers linking each node.

Understanding the time and space complexity of linked list operations is crucial when analyzing and designing algorithms for robotics and computer vision applications.

xxxxxxxxxx

# Python code here

​

# Time Complexity

​

# Insertion - O(1)

# Deletion (at the beginning) - O(1)

# Deletion (at the end) - O(n)

# Deletion (at a specific position) - O(n)

# Traversal - O(n)

​

# Space Complexity

​

# Singly Linked List - O(n)

# Doubly Linked List - O(n)

# Circular Linked List - O(n)

Linked List vs Array

When considering data structures for storing and manipulating data, linked lists and arrays are two common options. Each has its own strengths and weaknesses, making them suitable for different use cases.

Arrays

Arrays are a fundamental data structure that allows for efficient storage and processing of elements. Here are some characteristics of arrays:

• Random Access: Arrays provide constant-time access to elements since they are stored in contiguous memory locations. This means you can access any element by its index in O(1) time.
• Fixed Size: Arrays have a fixed size determined during initialization. Once created, the size cannot be changed.
• Efficient for Iteration: Arrays are efficient for iterating over elements sequentially.

Here is an example of working with arrays in Python:

1numbers = [1, 2, 3, 4, 5]
2
3# Accessing the element at index 2
4element = numbers[2]
5print(f"Element at index 2: {element}")
6
7# Updating the element at index 3
8numbers[3] = 10
9
10# Inserting an element at the beginning
11numbers.insert(0, 0)
12
13# Deleting the element at index 4
14numbers.pop(4)
15
16# Printing all elements
17for num in numbers:
18    print(num, end=" ")
19print()

xxxxxxxxxx

#include <iostream>

#include <vector>

​

int main() {

  std::vector<int> myVector = {1, 2, 3, 4, 5};

​

  // Accessing the element at index 2

  int element = myVector[2];

  std::cout << "Element at index 2: " << element << std::endl;

​

  // Updating the element at index 3

  myVector[3] = 10;

​

  // Inserting an element at the beginning

  myVector.insert(myVector.begin(), 0);

​

  // Deleting the element at index 4

  myVector.erase(myVector.begin() + 4);

​

  // Printing all elements

  for (int i : myVector) {

    std::cout << i << " ";

  }

  std::cout << std::endl;

​

  return 0;

}

Applications of Linked Lists

Linked lists have various applications in robotics and computer vision. Here are a few examples:

• Image Galleries: In computer vision applications, linked lists can be used to store and manage collections of images. Each node in the linked list represents an image, with a reference to the next image in the sequence. This allows for easy navigation through the gallery and the ability to add or remove images dynamically.

Here's an example of implementing an image gallery using a linked list in Python:

1class Image:
2    def __init__(self, path):
3        self.path = path
4        self.next = None
5
6
7class ImageGallery:
8    def __init__(self):
9        self.head = None
10
11    def add_image(self, path):
12        new_image = Image(path)
13        if not self.head:
14            self.head = new_image
15        else:
16            current = self.head
17            while current.next:
18                current = current.next
19            current.next = new_image
20
21    def print_images(self):
22        current = self.head
23        while current:
24            print(current.path)
25            current = current.next
26
27# Create an image gallery
28
29
30# Add images to the gallery
31
32
33# Print all images in the gallery

• Path Planning: In robotics, linked lists can be used to represent paths or trajectories. Each node in the linked list represents a waypoint or point in the path, and the next node represents the next point to move to. This allows for smooth and efficient movement along a predefined path.

• Sensor Data Buffer: Linked lists can also be used to store and manage sensor readings in robotics. Each node in the list can contain a timestamped sensor reading, allowing for easy access to historical data and efficient memory management.

These are just a few examples of how linked lists can be applied in robotics and computer vision. Their flexibility and dynamic nature make them a valuable tool in various applications.

xxxxxxxxxx

gallery.print_images()

class Image:

    def __init__(self, path):

        self.path = path

        self.next = None

​

class ImageGallery:

    def __init__(self):

        self.head = None

​

    def add_image(self, path):

        new_image = Image(path)

        if not self.head:

            self.head = new_image

        else:

            current = self.head

            while current.next:

                current = current.next

            current.next = new_image

​

    def print_images(self):

        current = self.head

        while current:

            print(current.path)

            current = current.next

​

# Create an image gallery

gallery = ImageGallery()

​

# Add images to the gallery