Linked Lists | Notion

Intro

Nodes - hold certain data and pointers/references/links to other nodes

Pointers - reference to another node

Head - first node of the list

Tail - last node of the list, points to NULL

Linked List is a ADT that represents a linear collection of data elements where each element contains an address of the next element

Frame 5.png

Singly-Linked List

linked list where each node points to the next node and the last node points to null

Doubly-Linked List

linked list where each node has two pointers:
- next which points to the next node
- prev which points to the previous node
the prev pointer of the first node and the next pointer of the last node point to null

Circular Linked List

the last node points back to the first node

Circular Doubly Linked List

the prev pointer of the first node points to the last node
the next pointer of the last node points to the first node

Usage

used in List, Sparse Matrix, Queue & Stack implementation
used in separate chaining
used in the implementation of adjacency lists for graphs
dynamic memory allocation
undo functionality

Comparison

opposed to Arrays where data is stored in sequential blocks of memory, in a Linked List each element contains an address of the next element
Doubly-Linked List uses 2x memory than Singly-Linked List

Advantages

quick insertion and deletion
Doubly-Linked List can be traversed backwards

Disadvantages

access is linear because directly accessing elements by their position in the list is not possible (you have to traverse from the start)
Singly-Linked List can’t easily access previous elements

Problems

Corner Cases

empty linked list (head is null)
single node / two node
linked list has cycles
elements can be unsorted or sorted, can contain duplicate elements or all unique elements
can contain any type of data: strings, characters, numbers

Implementation

Time Complexity
Operations	Worst case
access()	`O(n)`
insert(node)	`O(1)` assumes you have traversed to the insertion position
remove(node)	`O(1)` assumes you have traversed to the node to be removed
search(node)	`O(n)`

Space Complexity
Implementation	Worst case
Linked List	`O(n)`

n is the number of nodes in the linked list

Algorithms

Patterns

‣

getting the kth node behind the last node:
- have two pointers, where one is k nodes ahead of the other
- when the node ahead reaches the end, the other node is k nodes behind
detecting cycles
- have two pointers, where one pointer increments twice as much as the other,
- if the two pointers meet, means that there is a cycle
getting the middle node
- have two pointers, where one pointer increments twice as much as the other
- when the faster node reaches the end of the list, the slower node will be at the middle

Sentinel/Dummy nodes

adding a sentinel/dummy node at the head and/or tail might help to handle many edge cases where operations have to be performed at the head or the tail
the presence of dummy nodes essentially ensures that operations will never have be done on the head or the tail, thereby removing a lot of headache in writing conditional checks to dealing with null pointers
be sure to remember to remove them at the end of the operation

Using space

many linked list problems can be easily solved by creating a new linked list and adding nodes to the new linked list with the final result
however, this takes up extra space and makes the question much less challenging
the interviewer will usually request that you modify the linked list in-place and the solve the problem without additional storage

Elegant modification operations

inked list's non-sequential nature of memory allows for efficient modification of its contents

Code

# Singly-Linked List
class Node:
    # create a node
    def __init__(self, data):
        self.data = data
        self.next = None

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

		# insert at the beginning
    def insertAtBeginning(self, new_data):
        new_node = Node(new_data)
        new_node.next = self.head
        self.head = new_node

    # insert after a node
    def insertAfter(self, prev_node, new_data):

        if prev_node is None:
            print("The given previous node must be in LinkedList.")
            return

        new_node = Node(new_data)
        new_node.next = prev_node.next
        prev_node.next = new_node

    # insert at the end
    def insertAtEnd(self, new_data):
        new_node = Node(new_data)

        if self.head is None:
            self.head = new_node
            return

        last = self.head
        while (last.next):
            last = last.next

        last.next = new_node

    # deleting a node
    def deleteNode(self, position):

        if self.head is None:
            return

        temp = self.head

        if position == 0:
            self.head = temp.next
            temp = None
            return

        # find the key to be deleted
        for i in range(position - 1):
            temp = temp.next
            if temp is None:
                break

        # if the key is not present
        if temp is None:
            return

        if temp.next is None:
            return

        next = temp.next.next

        temp.next = None

        temp.next = next

    # search an element
    def search(self, key):

        current = self.head

        while current is not None:
            if current.data == key:
                return True

            current = current.next

        return False

    # sort the linked list
    def sortLinkedList(self, head):
        current = head
        index = Node(None)

        if head is None:
            return
        else:
            while current is not None:
                # index points to the node next to current
                index = current.next

                while index is not None:
                    if current.data > index.data:
                        current.data, index.data = index.data, current.data

                    index = index.next
                current = current.next

    # print the linked list
    def printList(self):
        temp = self.head
        while (temp):
            print(str(temp.data) + " ", end="")
            temp = temp.next

if __name__ == '__main__':

		llist = LinkedList()
    llist.insertAtEnd(1)
    llist.insertAtBeginning(2)
    llist.insertAtBeginning(3)
    llist.insertAtEnd(4)
    llist.insertAfter(llist.head.next, 5)

    print('linked list:')
    llist.printList()

    print("\\nAfter deleting an element:")
    llist.deleteNode(3)
    llist.printList()

    print()
    item_to_find = 3
    if llist.search(item_to_find):
        print(str(item_to_find) + " is found")
    else:
        print(str(item_to_find) + " is not found")

    llist.sortLinkedList(llist.head)
    print("Sorted List: ")
    llist.printList()

Resources

What's a Linked List, Anyway? [Part 1]

What's a Linked List, Anyway? [Part 2]