Doubly Linked-List

⚠️ This post was created when I was in high school and is no longer maintained.

(here we temporarily ignore satellite data and only care about the key.)

Linked lists provide a simple, flexible representation for dynamic sets.

0. Basics

1. list properties: L.head
   • when L.head == NIL, L is empty;
   • L.head.prev == NIL
2. element properties: x.prev | x.key | x.next

1. Pseudocode

(1) Without sentinels

algorithm ListSearch(L, k):
    x := L.head
    While x != NIL and x.key != k do --> check for NIL before accessing its properties
        x = x.next
    return x  --> if the element we search for does not exist, this returns NIL, the next pointer of the last element.

algorithm ListInsert(L, x):
    x.next = L.head
    x.prev = NIL --> this is important as well. The prev pointer of the 1st node is NIL
    if L.head != NIL then --> if head is NIL, there is no L.head.prev (the 1st node)
        L.head.prev = x
    L.head = x

algorithm ListDelete(L, x):
    if x.prev != NIL then --> Whether it's the head or not
        x.prev.next = x.next
    else 
        L.head = x
    if x.next != NIL then --> Whether it's the tail or not
        x.next.prev = x.prev

Tips: - To delete a node by key, run listSearch() before listDelete(). - Deleting the head or tail is trickier—this is where a sentinel node helps.

(2) With sentinels

algorithm ListSearch(L, k):
    x := L.nil
    While x != L.nil.next and x.key != k do
        x = x.next
        
algorithm ListInsert(L, x):
    -- we need to change 4 pointers --
    x.next = L.nil.next
    x.prev = L.nil
    L.nil.next.prev = x
    L.nil.next = x

algorithm ListDelete(L, x):
    -- we need to bridge 2 pointers --
    x.next.prev = x.prev
    x.prev.next = x.next

2. Time complexity

1. ListSearch(): \(T(n) = \Theta(n)\)
2. ListInsert(node) && ListDelete(node): \(T(n) = O(1)\)

Tips:

• For singly linked-list, if we want to delete a node, we have to search its predecessor first.
• Reverse singly linked-list in linear time literative && recursive

3. Code

case class Node(var _key: Double = Double.PositiveInfinity, var _prev: Node = null, var _next: Node = null)

class LinkedList {
    private var _head: Node = null

    def listSearch(key: Double): Node = {
        var node = _head
        while (node != null && node._key != key) {
            node = node._next
        }
        return node
    }

    def listInsert(newNode: Node): Unit = {
        newNode._prev = null
        newNode._next = _head

        if (_head != null) {
            _head._prev = newNode
        }
        _head = newNode
    }

    def listDelete(node: Node): Unit = {
        if (node._prev != null) {
            node._prev._next = node._next
        } else {
            _head = node._next
        }

        if (node._next != null) {
            node._next._prev = node._prev
        }
    }

    override def toString(): String = {
        var list = "["
        var node = _head
        while (node != null) {
            list = list ++ " " ++ node._key.toString()
            node = node._next
        }
        return list ++ " ]"
    }
}

class SentinelLinkedList {
    private val _sentinel: Node = new Node()
    // Initialize _sentinel !!!
    _sentinel._prev = _sentinel
    _sentinel._next = _sentinel

    def listSearch(key: Double): Node = {
        // here should initialize node as _sentinel._next rather than _sentinel itself
        var node = _sentinel._next 
        while (node != _sentinel && node._key != key) {
            node = node._next
        }
        return node
    }

    def listInsert(newNode: Node): Unit = {
        newNode._prev = _sentinel
        newNode._next = _sentinel._next
        _sentinel._next._prev = newNode
        _sentinel._next = newNode
    }

    def listDelete(node: Node): Unit = {
        node._prev._next = node._next
        node._next._prev = node._prev
    }

    override def toString(): String = {
        var list = "<"
        var node = _sentinel._next
        while (node != _sentinel) {
            list = list ++ " " ++ node._key.toString()
            node = node._next
        }
        return list ++ " >"
    }
}

object DoublyLinkedListStructure {
    def main(args: Array[String]) = {
        // Test LinkedList:
        val linkedList = new LinkedList()
        println("New LinkedList: " ++ linkedList.toString)
        
        linkedList.listInsert(Node(10))
        linkedList.listInsert(Node(9))
        linkedList.listInsert(Node(8))
        linkedList.listInsert(Node(7))
        linkedList.listInsert(Node(6))
        linkedList.listInsert(Node(5))
        linkedList.listInsert(Node(4))
        linkedList.listInsert(Node(3))
        linkedList.listInsert(Node(2))
        linkedList.listInsert(Node(1))
        linkedList.listInsert(Node(0))
        println("After Insertion: " ++ linkedList.toString)

        linkedList.listDelete(linkedList.listSearch(0))
        linkedList.listDelete(linkedList.listSearch(8))
        linkedList.listDelete(linkedList.listSearch(9))
        linkedList.listDelete(linkedList.listSearch(10))
        println("After Delete: " ++ linkedList.toString)

        // Test SentinelLinkedList:
        val sentinelLinkedList = new SentinelLinkedList()
        println("New SentinelLinkedList: " ++ sentinelLinkedList.toString)

        sentinelLinkedList.listInsert(Node(10))
        sentinelLinkedList.listInsert(Node(9))
        sentinelLinkedList.listInsert(Node(8))
        sentinelLinkedList.listInsert(Node(7))
        sentinelLinkedList.listInsert(Node(6))
        sentinelLinkedList.listInsert(Node(5))
        sentinelLinkedList.listInsert(Node(4))
        sentinelLinkedList.listInsert(Node(3))
        sentinelLinkedList.listInsert(Node(2))
        sentinelLinkedList.listInsert(Node(1))
        sentinelLinkedList.listInsert(Node(0))
        println("After Insertion: " ++ sentinelLinkedList.toString)

        sentinelLinkedList.listDelete(sentinelLinkedList.listSearch(0))
        sentinelLinkedList.listDelete(sentinelLinkedList.listSearch(8))
        sentinelLinkedList.listDelete(sentinelLinkedList.listSearch(9))
        sentinelLinkedList.listDelete(sentinelLinkedList.listSearch(10))
        println("After Delete: " ++ sentinelLinkedList.toString)
    }
}