Singly Linked List

Python C++

push back $O(1)$
push front $O(1)$
pop back $O(N)$
pop front $O(1)$
find item $O(N)$

Description

Structure

Node Structure: A node in a singly linked list typically consists of two components: data and next pointer.

Data: It holds the actual value or data associated with the node.

Next Pointer: It stores the memory address (reference) of the next node in the list.

Head and Tail: The linked list is accessed through the head node, which points to the first node in the list. The last node in the list points to NULL, indicating the end of the list. This node is known as the tail node.

Push back

  1. Create a new node.
  2. Set the next pointer of tail node to the new node.
  3. Set the tail pointer to the new node.

Push front

  1. Create a new node.
  2. Set the next pointer of the new node to the head node.
  3. Set the head pointer to the new node.

Pop back

  1. Find the node with next pointer equal to the tail pointer.
  2. Free the tail node.
  3. Set the next pointer of the found node as NULL.
  4. Set the tail pointer to the found node.

Pop front

  1. Save the next pointer of the head node to the temporary pointer.
  2. Free the head node.
  3. Set the head pointer to the temporary pointer.

Find item

  1. Set current pointer to the head pointer.
  2. Compare current node data with finding item data in cycle:
    • If they are equal, we found the right node.
    • If they are not equal, set current pointer to the current node next pointer.
  3. If current node is NULL, then there is no right node in the list.

Example

Let's look at several examples of working with a singly linked list. We start with empty list.

Push front data = 1.
Push front data = 2.
Push back data = 3.
Pop front.
Pop back.
Find data = 4.

  1. Set current pointer to the head pointer.
  2. Current node data = 1 is not equal to data = 4.
  3. Set current pointer to the current node next pointer.


Find data = 4.
Current node is NULL, then there is no node with data = 4 in the list.

Code

Python 

                        class SinglyLinkedList:
                            class Node:
                                def __init__(self, data: Any):
                                    self.data = data
                                    self.next: Optional[SinglyLinkedList.Node] = None
                        
                            def __init__(self):
                                self.head: Optional[SinglyLinkedList.Node] = None
                                self.tail: Optional[SinglyLinkedList.Node] = None
                        
                            def push_back(self, data: Any):
                                if self.tail is None:
                                    self.tail = SinglyLinkedList.Node(data)
                                    self.head = self.tail
                                else:
                                    self.tail.next = SinglyLinkedList.Node(data)
                                    self.tail = self.tail.next
                        
                            def push_front(self, data: Any):
                                if self.head is None:
                                    self.head = SinglyLinkedList.Node(data)
                                    self.tail = self.head
                                else:
                                    new_head = SinglyLinkedList.Node(data)
                                    new_head.next = self.head
                                    self.head = new_head
                        
                            def pop_back(self):
                                if self.tail is not None:
                                    if self.head.next is None:
                                        self.head = None
                                        self.tail = None
                                    else:
                                        new_tail = self.head
                                        while new_tail.next.next is not None:
                                            new_tail = new_tail.next
                                        new_tail.next = None
                                        self.tail = new_tail
                        
                            def pop_front(self):
                                if self.head is not None:
                                    if self.head.next is None:
                                        self.head = None
                                        self.tail = None
                                    else:
                                        self.head = self.head.next
                        
                            def find_item(self, data: Any) -> bool:
                                current = self.head
                                while current is not None:
                                    if current.data == data:
                                        return True
                                    else:
                                        current = current.next
                                return False
C++