Abstract Data Types and Linked List Data Structures

Abstract Data Type (ADT)

• An Abstract Data Type (ADT) is a mathematical abstraction or model comprising a collection of objects together with a set of operations.

• ADTs specify what operations can be performed and their behavior, without detailing memory organization or implementation algorithms.

• Common ADT examples include:

  • List ADT

  • Stack ADT

  • Queue ADT

  • Priority Queue (Array, List, Heap)

  • Heap (Array, Tree)

  • Map (HashTable)

List ADT & Array Implementation

• A list contains $N$ elements of the same type arranged sequentially: $A_0, A_1, A_2, \dots, A_{N-1}$.

• Elements follow a strict precedence relationship where $A_i$ succeeds $A_{i-1}$ (for $i < N$) and precedes $A_{i+1}$.

• Core operations include Insert(x), Insert(x, 2), Remove(x), Find(), FindKth(k), Previous, and Next.

• Array implementations perform well for access and insertions at the end, but suffer worst-case $O(N)$ time complexity for insertions and deletions at the front due to element shifting.

Singly Linked List

• Consists of connected nodes, where each node holds a data element and a next link referencing its successor; the last node points to null.

• Time complexity breakdown:

  • Add node as first node: $O(1)$

  • Add node as last node: $O(1)$ (when keeping track of tail)

  • Remove first node: $O(1)$

  • Remove last node: $O(N)$ (requires traversing to find the node prior to tail)

  • Add/Remove node after a given node: $O(1)$

  • FindKth element: $O(N)$

  • Display all nodes: $O(N)$

• Insertion into a linked list requires updating two references.

• Deletion from a linked list is executed with a single reference change.

Doubly Linked List

• Each node (DNode) maintains three fields: one data field and two link fields (next and prev).

• Enables bidirectional traversal, allowing last-element removal and tail updates in constant time $O(1)$.

Linked List Variations

• List with Sentinel Nodes: Uses non-data dummy head and dummy tail nodes so that boundary links are never null.

• Header Linked List: Contains an extra header node at the start acting as a placeholder to simplify insertion, deletion, and traversal.

• Circular Singly Linked List: The next pointer of the final node points back to the first node for continuous traversal.

• Circular Doubly Linked List: The last node's next links to the header/first node, and the first node's prev links to the tail.

Questions & Discussion

• Question 1: How many links are required in Doubly Linked List?

• Question 2: Give structure of Single Linked List.