[Data Structure] Singly-Linked Lists

Singly-Linked List

 

Singly-Linked List is a data structure for implementing a list ADT, where each node has data and a pointer to the next node. 

The list structure typically has pointers to the list's first node and last node, called the head and tail, respectively.

A singly-linked list is a type of positional list: A list where elements contain pointers to the next and/or previous elements in the list. 

+) Null is a specific value indicating a pointer points to nothing.

 

singly-linked list diagram

In the diagram, after all the operations (create, append, prepend) are finished, 

The head node's data value is 66, and the tail node's data value is 44. 

 

 

---

Operations

 

1. Appending a Node

Append algorithm behavior differs if the list is empty or not empty:

• Empty: If the list's head pointer is null (empty), the algorithm points the list's head and tail pointers to the new node.
• Non-empty: If the list's head pointer is not null (not empty), the algorithm points the tail node's next pointer and the list's tail pointer to the new node.

 

 

2. Prepending a Node

Prepend algorithm behavior differs if the list is empty or not empty:

• Empty: If the list's head pointer is null (empty), the algorithm points the list's head and tail pointers to the new node.
• Non-empty: If the list's head pointer is not null (not empty), the algorithm points the new node's next pointer to the head node, and then points the list's head pointer to the new node.

 

 

3. Insert a Node

Given a new node, InsertAfter operation for a singly-linked list inserts the new node after a provided existing list node.

The InsertAfter algorithm considers three insertion scenarios:

• Insert as list's first node: If the list's head pointer is null, the algorithm points the list's head and tail pointers to the new node.
• Insert after list's tail node: If the list's head pointer is not null (list not empty) and curNode points to the list's tail node, the algorithm points the tail node's next pointer and the list's tail pointer to the new node.
• Insert in middle of list: If the list's head pointer is not null (list not empty) and curNode does not point to the list's tail node, the algorithm points the new node's next pointer to curNode's next node, and then points curNode's next pointer to the new node.

 

 

4. Removing a Node

Given a specified existing node in a singly-linked list, the RemoveAfter operation removes the node after the specified list node.

• Remove list's head node (special case): If curNode is null, the algorithm points sucNode to the head node's next node, and points the list's head pointer to sucNode. If sucNode is null, the only list node was removed, so the list's tail pointer is pointed to null (indicating the list is now empty).
• Remove node after curNode: If curNode's next pointer is not null (a node after curNode exists), the algorithm points sucNode to the node after curNode's next node. Then curNode's next pointer is pointed to sucNode. If sucNode is null, the list's tail node was removed, so the algorithm points the list's tail pointer to curNode (the new tail node).

 

 

5. Searching a Node

Given a key, a search algorithm returns the first node whose data matches that key, or returns null if a matching node was not found.

A simple linked list search algorithm checks the current node (initially the list's head node), returning that node if a match, else pointing the current node to the next node and repeating. If the pointer to the current node is null, the algorithm returns null (matching node was not found).

 

 

---

Python Implementation

 

To construct a list in Python, we need to use classes for both nodes and singly-linked lists.

Let's check out how Node and LinkedList class can be defined.

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


class LinekdList:
    def __init__(self):
        self.head = None
        self.tail = None

 

Now, let's check the implementation of each operation.

 

1. append

def append(self, new_node):
    if self.head is None:
        self.head = new_node
        self.tail = new_node
    else:
        self.tail.next = new_node
        self.tail = new_node

 

2. prepend

def prepend(self, new_node):
    if self.head is None:
        self.head = new_node
        self.tail = new_node
    else:
        new_node.next = self.head
        self.head = new_node

 

3. insert_after

def insert_after(self, current_node, new_node):
    if self.head is None:
        self.head = new_node
        self.tail = new_node
    elif current_node is self.tail:
        self.append(new_node)
    else:
        new_node.next = current_node.next
        current_node.next = new_node

 

4. remove_after

def remove_after(self, current_node):
    # Special case, remove head
    if (current_node is None) and (self.head is not None):
        succeeding_node = self.head.next
        self.head = succeeding_node

        if succeeding_node is None:  # When removed the final item
            self.tail = None

    elif current_node is not None:
        succeeding_node = current_node.next.next
        current_node.next = succeeding_node

        if succeeding_node is None:
            self.tail = current_node

 

 

Final implementation of singly-linked list with few basic operaitons:

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


class LinekdList:
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, new_node):
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node

    def prepend(self, new_node):
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.next = self.head
            self.head = new_node

    def insert_after(self, current_node, new_node):
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        elif current_node is self.tail:
            self.append(new_node)
        else:
            new_node.next = current_node.next
            current_node.next = new_node

    def remove_after(self, current_node):
        # Special case, remove head
        if (current_node is None) and (self.head is not None):
            succeeding_node = self.head.next
            self.head = succeeding_node

            if succeeding_node is None:  # When removed the final item
                self.tail = None

        elif current_node is not None:
            succeeding_node = current_node.next.next
            current_node.next = succeeding_node

            if succeeding_node is None:
                self.tail = current_node