Linked Lists

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.

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

# Creating nodes
player1 = Node(24)
player2 = Node(8)
player3 = Node(23)

# Linking the nodes
player1.next = player2
player2.next = player3

Which of the following statements about linked lists is true?

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:

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


# Create a singly linked list
linked_list = SinglyLinkedList()

# Insert elements
linked_list.insert_at_end(10)
linked_list.insert_at_end(20)
linked_list.insert_at_end(30)

# Display the linked list
linked_list.display()

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

```py
# 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)
                current = current.next


# Create a singly linked list
linked_list = SinglyLinkedList()

# Insert elements
linked_list.insert_at_end(10)
linked_list.insert_at_end(20)
linked_list.insert_at_end(30)

# Display the linked list
linked_list.display()
```

A singly linked list can only be traversed in one direction.

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:

```python
## 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


# Create a doubly linked list
linked_list = DoublyLinkedList()

# Append elements
linked_list.append(10)
linked_list.append(20)

# Display the linked list
linked_list.display()
```

A doubly linked list allows for efficient traversal in both directions.

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.

```python
# 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:
                print(temp.data, end=' ')
                temp = temp.next
                if temp == self.head:
                    break

# Create a circular linked list
cll = CircularLinkedList()
cll.append(1)
cll.append(2)
cll.append(3)
cll.append(4)

# Display the circular linked list
cll.display()
```

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 _________. 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.

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}}

```python
# 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:
            self.head = temp.next
            return
        while temp.next:
            if temp.next.data == data:
                temp.next = temp.next.next
                return
            temp = temp.next

    # Traversal operation
    def traverse(self):
        temp = self.head
        while temp:
            print(temp.data)
            temp = temp.next

# Create a linked list
llist = LinkedList()

# Insert elements
llist.insert(5)
llist.insert(10)
llist.insert(15)

# Delete element
llist.delete(10)

# Traverse the linked list
llist.traverse()
```

Insertion refers to _________________ an element to a linked list.

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.

```python
# 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)
```

What is the time complexity of inserting a node at the end of a singly linked list?

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:

numbers = [1, 2, 3, 4, 5]

# Accessing the element at index 2
element = numbers[2]
print(f"Element at index 2: {element}")

# Updating the element at index 3
numbers[3] = 10

# Inserting an element at the beginning
numbers.insert(0, 0)

# Deleting the element at index 4
numbers.pop(4)

# Printing all elements
for num in numbers:
    print(num, end=" ")
print()

```
#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;
}
```

Which of the following statements is true about linked lists and arrays?

A) Linked lists provide constant-time access to elements B) Arrays have a fixed size that cannot be changed C) Linked lists are efficient for iterating over elements sequentially D) Arrays are suitable for dynamic data storage and manipulation

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:

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


# Add images to the gallery


# 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.

```py

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
gallery.add_image('image1.jpg')
gallery.add_image('image2.jpg')
gallery.add_image('image3.jpg')

# Print all images in the gallery
gallery.print_images()
```

Which of the following is an application of linked lists?

Generating complete for this lesson!