Data Structure (2) - Singly and Doubly Linked List

• What is a linked list?
• Where are linked lists used?
• Terminology
• Singly vs Doubly Linked Lists
• Singly & Doubly Linked lists Pros and Cons
• Implement Insert & Remove
• Complexity
• Python Code
  • Singly Linked List
  • Insert
  • Remove

What is a linked list?

A linked list is a sequential list of nodes that hold data which point to other nodes also containing data.

Where are linked lists used?

• Used in many List, Queue & Stack implementations.
• Great for creating circular lists.
• Can easily model real word objects such as trains.
• Used in separate chaining, which is present certain Hashtable implementations to deal with hashing collisions.
• Often used in the implementation of adjacency lists for graphs.

Terminology

Head: The first node in a liked list

Tail: The last node in a linked list

Pointer: Reference to another node

Node: An object containing data and pointer(s)

Singly vs Doubly Linked Lists

Singly liked lists only hold a reference to the next node. In the implementation you always maintain a reference to the head to the linked list and a reference to the tail node for quick additions/removals.

With a doubly linked list each node holds a reference to the next and previous node. In the implementation you always maintain a reference to the head and the tail of the doubly linked list to do quick additions/ removals from both ends of your list.

Singly & Doubly Linked lists Pros and Cons

Type	Pros	Cons
Singly Linked	Use less memory. Simpler implementation	Cannot easily access previous elements
Doubly Linked	Can be traversed backwards	Takes 2x memory

Implement Insert & Remove

The main point of implementation is pointer.

Scenario: Insert 21 where the third node is

Insert a new node can be summarize as steps below.

1. Use pointer to find the previous node of third node.
2. Create new node.
3. Make new node point to next node.
4. Make pointer pointing node point to new node.

Result:

Scenario: Remove 11 from linked list

Remove existed node can be summarize as steps below.

1. Use two pointer and keep traveling until second pointer find target node.

2. Create tmp pointer for target node and move pointer to next.
3. Let pointer 1 node point to pointer 2 node.

4. Remove target node.

Result:

Complexity

Action	Singly	Doubly
Search	$O(n)$	$O(n)$
Insert at Head	$O(1)$	$O(1)$
Insert as tail	$O(1)$	$O(1)$
Remove at Head	$O(n)$	$O(1)$
Remove in middle	$O(n)$	$O(n)$

Python Code

Singly Linked List

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


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

    def insert(self, val: int, idx: int):

        node = Node(val)
        if not self.head:
            self.head = node
            return

        ptr = self.head
        count = 1

        while count < idx:
            ptr = ptr.next
            count += 1

        node.next = ptr.next
        ptr.next = node

    def remove(self, val: int):

        if not self.head:
            return

        ptr1 = self.head
        ptr2 = self.head.next

        if ptr1.val == val:
            self.head = ptr2
            return

        if not ptr2:
            return

        while ptr2.val != val:
            ptr1 = ptr2
            ptr2 = ptr2.next
            if not ptr2:
                return

        tmp = ptr2
        ptr2 = ptr2.next
        ptr1.next = ptr2
        del tmp

    def append(self, val):

        node = Node(val)
        if not self.head:
            self.head = node
            return

        ptr = self.head
        while ptr.next:
            ptr = ptr.next
        ptr.next = node

    def print_list(self):

        if not self.head:
            return ""

        ptr = self.head
        while ptr:
            print(ptr.val, end=" ")
            ptr = ptr.next
        print("\n")

Insert

Usage:

my_list = LinkedList()

print("Create linked list:")
my_list.append(42)
my_list.append(19)
my_list.append(7)
my_list.append(11)
my_list.append(34)
my_list.print_list()

print("Insert 21 where the third node is:")
my_list.insert(21, 3)
my_list.print_list()

Output:

Create linked list:
42 19 7 11 34 

Insert 21 where the third node is:
42 19 7 21 11 34 

Remove

Usage:

my_list = LinkedList()

print("Create linked list:")
my_list.append(42)
my_list.append(19)
my_list.append(7)
my_list.append(11)
my_list.append(34)
my_list.print_list()

print("Remove 11 from linked list:")
my_list.remove(11)
my_list.print_list()

Output:

Create linked list:
42 19 7 11 34 

Remove 11 from linked list:
42 19 7 34