Updated:

⚠️ 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):
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.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)

algorithm ListDelete(L, x):
if x.prev != NIL then --> Whether it's the head or not
x.prev.next = x.next
else
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)

private var _head: Node = null

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

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

}
}

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

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

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

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 ++ " >"
}
}

def main(args: Array[String]) = {