Doubly Linked-List

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

( hereby, we temporarily ignore the 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 --> be careful that we are supposed to check NIL before accessing its properties.
        x = x.next
    return x  --> if the element that we search does not exist, then this will return the next element of the last elemt=nt which is NIL.

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 --> this is necessary because 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: - if we want to delete a node with a certain key, then listSearch() is needed before listDelete() - for listDelete(), it’s a little bit troublesome when the x is the head or the tail (here is the place where the so-called sentinel node comes into play)

(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)
    }
}