The Project | About Us | Contribute | Donations | License

HOME

In this section, we will reinforce the concepts learned in the previous modules about lists through practical exercises. Each exercise will be followed by a detailed solution to help you understand the implementation and logic.

Exercise 1: Implement a Singly Linked List

Problem Statement

Implement a singly linked list with the following operations:

insert_at_beginning(data): Insert a node at the beginning of the list.
insert_at_end(data): Insert a node at the end of the list.
delete_node(data): Delete the first node with the given data.
display(): Display the contents of the list.

Solution

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

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

    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 = self.head
        while last.next:
            last = last.next
        last.next = new_node

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

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

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

        if temp == None:
            return

        prev.next = temp.next
        temp = None

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

# Example usage
sll = SinglyLinkedList()
sll.insert_at_beginning(10)
sll.insert_at_end(20)
sll.insert_at_end(30)
sll.display()  # Output: 10 -> 20 -> 30 -> None
sll.delete_node(20)
sll.display()  # Output: 10 -> 30 -> None

Explanation

Node Class: Represents each node in the list with data and next attributes.
SinglyLinkedList Class: Contains methods to manipulate the list.
- insert_at_beginning(data): Creates a new node and sets it as the head.
- insert_at_end(data): Traverses to the end of the list and adds the new node.
- delete_node(data): Finds and removes the node with the specified data.
- display(): Prints the list elements.

Exercise 2: Implement a Doubly Linked List

Problem Statement

Implement a doubly linked list with the following operations:

insert_at_beginning(data): Insert a node at the beginning of the list.
insert_at_end(data): Insert a node at the end of the list.
delete_node(data): Delete the first node with the given data.
display(): Display the contents of the list.

Solution

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

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

    def insert_at_beginning(self, data):
        new_node = Node(data)
        new_node.next = self.head
        if self.head is not None:
            self.head.prev = new_node
        self.head = new_node

    def insert_at_end(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node
        new_node.prev = last

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

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

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

        if temp == None:
            return

        if temp.next is not None:
            temp.next.prev = temp.prev

        if temp.prev is not None:
            temp.prev.next = temp.next

        temp = None

    def display(self):
        temp = self.head
        while temp:
            print(temp.data, end=" <-> ")
            temp = temp.next
        print("None")

# Example usage
dll = DoublyLinkedList()
dll.insert_at_beginning(10)
dll.insert_at_end(20)
dll.insert_at_end(30)
dll.display()  # Output: 10 <-> 20 <-> 30 <-> None
dll.delete_node(20)
dll.display()  # Output: 10 <-> 30 <-> None

Explanation

Node Class: Represents each node in the list with data, next, and prev attributes.
DoublyLinkedList Class: Contains methods to manipulate the list.
- insert_at_beginning(data): Creates a new node and sets it as the head, updating the previous head's prev pointer.
- insert_at_end(data): Traverses to the end of the list and adds the new node, updating the previous last node's next pointer.
- delete_node(data): Finds and removes the node with the specified data, updating the next and prev pointers of adjacent nodes.
- display(): Prints the list elements.

Exercise 3: Implement a Circular Linked List

Problem Statement

Implement a circular linked list with the following operations:

insert_at_beginning(data): Insert a node at the beginning of the list.
insert_at_end(data): Insert a node at the end of the list.
delete_node(data): Delete the first node with the given data.
display(): Display the contents of the list.

Solution

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

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

    def insert_at_beginning(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            new_node.next = self.head
        else:
            temp = self.head
            while temp.next != self.head:
                temp = temp.next
            new_node.next = self.head
            temp.next = new_node
            self.head = new_node

    def insert_at_end(self, data):
        new_node = Node(data)
        if not self.head:
            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 delete_node(self, data):
        if self.head is None:
            return

        if self.head.data == data:
            if self.head.next == self.head:
                self.head = None
            else:
                temp = self.head
                while temp.next != self.head:
                    temp = temp.next
                temp.next = self.head.next
                self.head = self.head.next
            return

        prev = None
        temp = self.head
        while temp.next != self.head:
            if temp.data == data:
                break
            prev = temp
            temp = temp.next

        if temp.data == data:
            prev.next = temp.next
            temp = None

    def display(self):
        if not self.head:
            print("List is empty")
            return
        temp = self.head
        while True:
            print(temp.data, end=" -> ")
            temp = temp.next
            if temp == self.head:
                break
        print("HEAD")

# Example usage
cll = CircularLinkedList()
cll.insert_at_beginning(10)
cll.insert_at_end(20)
cll.insert_at_end(30)
cll.display()  # Output: 10 -> 20 -> 30 -> HEAD
cll.delete_node(20)
cll.display()  # Output: 10 -> 30 -> HEAD

Explanation

Node Class: Represents each node in the list with data and next attributes.
CircularLinkedList Class: Contains methods to manipulate the list.
- insert_at_beginning(data): Creates a new node and sets it as the head, updating the last node's next pointer to point to the new head.
- insert_at_end(data): Traverses to the end of the list and adds the new node, updating the last node's next pointer to point to the new node, and the new node's next pointer to point to the head.
- delete_node(data): Finds and removes the node with the specified data, updating the next pointer of the previous node.
- display(): Prints the list elements in a circular manner.

Conclusion

In this section, we have covered exercises on implementing singly linked lists, doubly linked lists, and circular linked lists. Each exercise included a problem statement, solution, and detailed explanation to help you understand the concepts and their implementations. Practice these exercises to solidify your understanding of lists and their operations.

Exercises with Lists

Exercise 1: Implement a Singly Linked List

Problem Statement

Solution

Explanation

Exercise 2: Implement a Doubly Linked List

Problem Statement

Solution

Explanation

Exercise 3: Implement a Circular Linked List

Problem Statement

Solution

Explanation

Conclusion

Data Structures Course

Module 1: Introduction to Data Structures

Module 2: Lists

Module 3: Stacks

Module 4: Queues

Module 5: Trees

Module 6: Graphs

Module 7: Conclusions and Additional Resources