Data Structures - Part 2

Data Structures - Part 2

Data Structures (Abstract Data Types) - Part 2 (Linked List)

Refer this article for Part 1 (Array) of the series.

2. Linked List

A linked list is a linear data structure where elements are stored in nodes. Each node consists of two parts: data (which holds the value) and a reference (or pointer) to the next node in the sequence. In contrast to arrays, elements (nodes) in a linked list are not stored in contiguous memory locations but instead are connected via pointers. Unlike arrays, linked lists are dynamic and can grow or shrink in size as needed. They do not have a built-in length property, though such feature can be implemented in custom classes. To determine the number of elements in a linked list, we typically need to traverse the entire list and count the nodes.

This structure which involves updating pointers, makes insertions and deletions faster since it avoids the need to shift elements, in contrast to arrays. However, linked lists do not allow direct access to elements by index. To access a specific element, we must traverse the list from the head (the first node) to the desired node. Attempting to access or delete a non-existent node in a linked list can trigger an exception (Python - AttributeError), requiring proper exception handling strategy.

Linked lists come in several variations, including:

  • Single Linked List: Each node points only to the next node.
  • Double Linked List: Each node contains references to both the next and the previous nodes.
  • Circular Linked List: The last node in the list points back to the head, forming a loop.

Each type is suited to different use cases depending on the operations required. In this article we will be implementing a single linked list with Python.


We have to follow an object oriented approach to implement a linked list. We use two classes; a LinkedList class to create the entire linked list object and a Node class to create each node object in a linked list. In the Node class we define the constructor to take the current object (self) and data as arguments. Inside the constructor, we assign self.next to None. In the LinkedList class constructor, we assign self.head to None since it is the first node of the linked list and the linked list is empty initially.

The code snippet, linkedlist = LinkedList(), calls the LinkedList class constructor and initializes the head node, thereby creates a new linked list object. Now to create each individual nodes we’ll define the function insert. This function takes the data in its arguments and pass it to the Node class via new_node = Node(data). This creates a new node with the given data and assign it to the variable new_node. We will iterate through a values list: [10, 20, 30, 40, 50], and insert them to the linked list one at a time.

Inside the insert function, we implement an if-else condition to check if we insert values for the first time. Initially -when the linked list is empty-, self.head equals to None. We negate this by using not keyword thereby, making the if statement accessible. Inside the if statement, we assign the newly created node to the head. So, now head.data will be 10 and head.next will be None.

Our second function call, triggers creating the second new node with a value of 20. This time if condition will be skipped since now the head is not empty. Inside the else condition, we initialize a temporary variable current, to traverse through the nodes, starting with head. While current.next is not None, while loop will iterate through the nodes, assigning current.next to current . Once we reach the end, while loop will be skipped and new_node will be inserted to the last None space.

So far, we have two nodes in our linked list. First is the head node with 10 as the value and points to the node with 20 as the value. Second node with 20 as the value points to None. The third function call, will create another new node and append it as the third node of the linked list, after the node with value 20. This will repeat until all the values in the list are inserted to the linked list.

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


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

    def insert(self, data):
        new_node = Node(data)

        # Initial insert (at head)
        if not self.head:
            self.head = new_node

        # Insert at the end
        else:
            current = self.head

            while current.next:
                current = current.next

            current.next = new_node


linkedlist = LinkedList()

for i in [10, 20, 30, 40, 50]:
    linkedlist.insert(i)

  • Inserting an element at the beginning(head) has O(1) time and space complexity as it only requires a one time pointer update with no additional space required except the new node itself.

  • Inserting an element at the end has O(n) time and O(1) space complexity since traversal is required to find the correct position and no additional space is required except the new node itself.


Now let’s implement the display function. Since linked lists do not have indexes we are implementing the function to traverse through the entire linked list and output the node values one at a time. This function traverses through the entire list starting from the head. We need a temporary variable current to traverse through the list. We have used a while loop to print the data and move the variable reference to the next node. Alternatively, we can append the data of each node (elements) in a new Python list while traversing through the linked list, and return the new list.

    def display(self):
        current = self.head

        while current:
            print(current.data)
            current = current.next

        # # Display as a list
        # elements = []
        # current = self.head

        # while current:
        #     elements.append(current.data)
        #     current = current.next

        # print(elements)


linkedlist.display()

  • Displaying elements without creating a new list has O(n) time and O(1) space complexity since traversal is required to find the correct position and no additional space is required.

  • Displaying elements by creating a new list has O(n) time and O(n) space complexity since traversal is required to find the correct position and the new list will be created with space for n elements.


Now let’s implement the search function. Similar to the display function, we need a temporary variable current to traverse through the list. We have used a while loop to iterate through the linked list till we find the key value in the list. If a node with the data equal to the key is found, it returns f"{key} found.". If the traversal finishes without finding the key, it returns f"{key} not found.".

    def search(self, key):
        current = self.head

        while current:
            if current.data == key:
                return f"{key} found."
            current = current.next

        return f"{key} not found."


print(linkedlist.search(10))  # first
print(linkedlist.search(50))  # last
print(linkedlist.search(30))  # middle
print(linkedlist.search(90))  # not found
  • Searching for an element has O(n) time and O(1) space complexity since traversal is required to find the correct position and no additional space is required.

Now let’s implement the delete function. First, we initialize two temporary variables; current and previous to keep track of current and previous nodes while traversing the linked list. Then we check if the head node contains the key; if current and current.data == key. If so, the head is assigned with the next node (self.head = current.next), and thereby old head node is unlinked (deleted). If the head node doesn’t contain the key, we use a while loop to iterate through the linked list and update current and previous pointers until we find the node to be deleted.

After the while loop ends, if the node containing the key is found if current is not None, the current pointer’s next node is assigned to the previous pointer’s next node prev.next = current.next, thereby the current node is unlinked from the previous and next nodes. If the key is not found, the function will return a message f"{key} not found."

    def delete(self, key):
        current = self.head
        previous = None

        # Delete at head
        if current and current.data == key:
            self.head = current.next
            return f"{key} deleted at the head node"

        # Traverse to find the key
        while current and current.data != key:
            previous = current
            current = current.next

        # Delete at the end/ middle
        if current is not None:
            previous.next = current.next
            return f"{key} deleted."

        # Key not found
        return f"{key} not found."


print(linkedlist.delete(10))  # first
print(linkedlist.delete(50))  # last
print(linkedlist.delete(30))  # middle
print(linkedlist.delete(90))  # not found

linkedlist.display()

  • Deleting an element at the beginning(head) has O(1) time and space complexity as it only requires a one time pointer update with no additional space required.

  • Deleting an element at the end or middle has O(n) time and O(1) space complexity since traversal is required to find the correct position and no additional space is required.


Complete Code Example

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


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

    def insert(self, data):
        new_node = Node(data)

        # Initial insert (at head)
        if not self.head:
            self.head = new_node

        # Insert at the end
        else:
            current = self.head

            while current.next:
                current = current.next

            current.next = new_node

    def display(self):
        current = self.head

        while current:
            print(current.data)
            current = current.next

        # # Display as a list
        # elements = []
        # current = self.head

        # while current:
        #     elements.append(current.data)
        #     current = current.next

        # print(elements)

    def search(self, key):
        current = self.head

        while current:
            if current.data == key:
                return f"{key} found."
            current = current.next

        return f"{key} not found."

    def delete(self, key):
        current = self.head
        previous = None

        # Delete at head
        if current and current.data == key:
            self.head = current.next
            return f"{key} deleted at the head node"

        # Traverse to find the key
        while current and current.data != key:
            previous = current
            current = current.next

        # Delete at the end/ middle
        if current is not None:
            previous.next = current.next
            return f"{key} deleted."

        # Key not found
        return f"{key} not found."


linkedlist = LinkedList()

for i in [10, 20, 30, 40, 50]:
    linkedlist.insert(i)

linkedlist.display()

print(linkedlist.search(10))  # first
print(linkedlist.search(50))  # last
print(linkedlist.search(30))  # middle
print(linkedlist.search(90))  # not found


print(linkedlist.delete(10))  # first
print(linkedlist.delete(50))  # last
print(linkedlist.delete(30))  # middle
print(linkedlist.delete(90))  # not found

linkedlist.display()

Comments

Post a Comment

Popular posts from this blog

Data Structures - Part 1

Data Structures - Part 1 Data Structures (Abstract Data Types) - Part 1 (Array) Data structures are specific methods of organizing and storing collections of data in a way that enables efficient access and manipulation. In a previous article , we discussed python specific data structures (built-in data types: list, tuple, set & dictionary) . In this series of articles, we will explore common abstract data types (ADTs) that are language-agnostic. These ADTs can be classified into two categories: linear and non- linear. Linear data structures; Array , Linked List , Stack , Queue Non-linear data structures; Tree , Hash Map , Graph 1. Array Arrays are one of the most fundamental data structures, designed to store collections of data (elements) of the same data type . These elements are stored in contiguous memory locations, allowing access to each element using its index. Arrays are prone to an exception if accessed with an index that exceeds the array’s boun...
Read more

OOP with Python - Part 2

OOP with Python - Part 2 OOP with Python - Part 2 We covered the basics of Object-Oriented Programming (OOP) , including Classes and Objects, Encapsulation, and Inheritance in OOP with Python - Part 1 . In this second part, we will discuss the remaining two key principles of OOP; Abstraction and Polymorphism . Abstraction Abstraction is the concept of hiding the complex implementation details of a system and exposing essential features of an object. This allows us to focus on what an object does but not how it is done. This can reduce programming complexity and enhance code maintainability. In Python, abstraction can be achieved using abstract classes and methods provided by the abc module. An abstract class is a class that cannot be instantiated and typically contains one or more abstract methods. An abstract method is a method that is declared but contains no implementation. Subclasses of the abstract class must provide implementations for all abstract m...
Read more

OOP with Python - Part 1

OOP with Python - Part 1 OOP with Python - Part 1 OOP ( Object Oriented Programming ) is a programming paradigm (a design style or an approach with its related design principles and techniques) which considers objects as the primary building block of a software program. In our previous articles, we were following a procedural approach where we were writing our code in a sequential manner. As compared to the procedural approach, OOP provides benefits like modularity, ease of maintenance, flexibility, scalability and reusability which makes it ideal for large scale real world projects. Python, being a general purpose language, supports both procedural and OOP paradigms. So, in this article let’s talk about the basics of OOP and how to implement them in Python. Class & Object An object is a real world entity with properties (aka attributes or data or members) and behaviors (aka methods or functions). For instance, a cat is an object. It has a name, color ...
Read more