Linked List

Abstract

Developed in 1955 by Allen Newell, Cliff Shaw, and Herbert A. Simon at RAND Corporation, the linked list is a dynamically allocated data structure that grows as needed in memory. It bypasses the contiguous allocation constraints of standard Array Lists by linking scattered node containers via explicit system pointers.

• Category: Dynamic Linked Structures
• Core Node Anatomy: Formed of an internal data value paired with directional address pointers.
• Entry Constraints: Direct access is restricted to boundary head and tail pointers; finding interior elements requires sequential traversal.

---

Structural Variations

Linked Lists are configured into two primary architectural variants based on pointer depth:

Architectural Feature	Singly-Linked List	Doubly-Linked List
Pointers per Node	1 (Points exclusively forward to the next node)	2 (Points symmetrically to next and previous nodes)
Traversal Direction	Unidirectional (Forward only)	Bidirectional (Forward and backward)
Termination Bounds	Final node’s next reference points to NULL	head.prev and tail.next point to NULL

Structural Illustrations

Access Limitations Complexity

If direct structural references are limited to head or tail markers, finding a node inside a Linked List containing $n$ elements incurs an $O(n)$ linear time complexity, as the system must step through the pointer chain node-by-node.

---

Core Operations

Searching & Value Traversal

Finding an item or resolving an index requires sequential traversal from boundary references.

• Time Complexity: $O(n)$ worst-case.
• Optimization: In a Doubly-Linked List, if the requested index sits closer to the trailing margin, the routine can start at the tail and step backward to halve traversal overhead.

Algorithm 17 Linked List Search Algorithms

procedure FindByElement($element, head$)

$current \gets head$

while $current \neq \text{NULL}$ do

if $current.data == element$ then

return $\text{true}$

$current \gets current.next$

return $\text{false}$

procedure FindByIndex($index, head, n$)

if $index < 0$ or $index \ge n$ then

return $\text{NULL}$

$current \gets head$

for $i \gets 0 \text{ to } index - 1$ do

$current \gets current.next$

return current

Element Insertion

Inserting an element requires locating the node preceding the target position and updating neighboring pointers to splice in the new node container.

• Time Complexity: $O(1)$ at boundary margins (head/tail); $O(n)$ for internal positions due to the traversal cost of locating the insertion site.

Algorithm 18 Doubly Linked List Insertion

procedure Insert($newnode, index, head, tail, size$)

if $index == 0$ then

$newnode.next \gets head$

$head.prev \gets newnode$

$head \gets newnode$

else if $index == size$ then

$newnode.prev \gets tail$

$tail.next \gets newnode$

$tail \gets newnode$

else

$curr \gets head$

for $i \gets 0 \text{ to } index - 2$ do

$curr \gets curr.next$

$newnode.next \gets curr.next$

$newnode.prev \gets curr$

$curr.next \gets newnode$

$newnode.next.prev \gets newnode$

$size \gets size + 1$

Element Removal

Bypasses a targeted node by linking its preceding and succeeding neighbors directly to each other.

• Time Complexity: $O(1)$ at boundary edges; $O(n)$ for internal nodes.

Algorithm 19 Doubly Linked List Removal

procedure Remove($index, head, tail, n$)

if $index == 0$ then

$head \gets head.next$

$head.prev \gets \text{NULL}$

if $index == n - 1$ then

$tail \gets tail.prev$

$tail.next \gets \text{NULL}$

else

$curr \gets head$

for $i \gets 0 \text{ to } index - 2$ do

$curr \gets curr.next$

$curr.next \gets curr.next.next$

$curr.next.prev \gets curr$

$n \gets n - 1$

Memory Cleanup Realities

In the removal diagram, the decoupled node remains stranded in system space. From a strict data structure interface perspective, this does not break functionality because the item is unreachable. However, in non-garbage-collected environments (like C++), you must explicitly delete the unlinked node to avoid memory leaks.

---

Architectural Comparison Matrix

Technical Feature	Linked List Implementation	Array List Implementation
Access / Search Cost	$O(n)$ linear pointer sequence traversal	$O(1)$ random access / $O(\log n)$ sorted binary search
Head Insert / Delete	$O(1)$ quick pointer reassignment swap	$O(n)$ linear data block shifting
Tail Insert / Delete	$O(1)$ direct pointer assignment	Amortized $O(1)$ capacity shifting
Memory Footprint	Dynamic growth layout; no empty pre-allocated slots	Bounded continuous chunks; can leave unused margins
Pointer Overhead	Higher cost due to storing address references	Minimal cost; tracks data elements only

---

Related Notes

• Array Lists
• Circular Arrays
• Skip Lists