Remember that

base on which we develop algorithms to solve problems.

Organization & Logical Structure

The Organization, equivalently, the logical structure of data, is the intrinsic property of data, which determines the relationship between data elements and the operations on them, and it is independent from the storage.

A simple example is the hash table, which realizes the mapping

by storing entries at locations $\{\text{Hash}(\text{key})\}$. The hash function provides only a storage structure; it does not impose any logical relationship between elements. Now consider the case where keys are taken from $([n])$ and values from a given data type

If a predecessor–successor relationship is defined(that is, we can traverse from one element to the next by $f(a_k.\texttt{next}))$, the logical structure is a linear list. If not, the logical structure is merely a set, even though the data is stored via $([n])$, which is a sequential storage structure.

This illustrates that logical structure is intrinsic, while storage structure is extrinsic. The former is determined by the nature of the data, while the latter is determined by the implementation of the data structure.

Density of Storage Structure

Linear List

Linear list is a finite tuple of $n$ ($n\ge 0$) data elements

with the concept of a head $a_1$ and a tail $a_n$, where each element has a unique predecessor and a unique successor, except for the head and tail. Fundemental operations on a linear list include

• Initialize/Destroy/Print
• Length/Empty
• Locate/Search/Insert/Delete

Generally speaking, linked lists(a storage structure) are more likely to illustrate the logical structure of a linear list.

Sequential List

A sequential list stores a linear list in a contiguous block of memory. Each element $a_i$ is placed at a physical address

It can be statically allocated (fixed size) or dynamically allocated (resizable) as follows, taking a dynamic array $L$ consisting of $\texttt{ElemType}$ elements as an example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

#include <stdlib.h> // for malloc
typedef int ElemType; // or any other type

// content above and some safe checks below will be omitted for brevity

#define InitSize 100
typedef struct {
    ElemType *data;
    int MaxSize, length;
} SqList;

SqList *InitList() {
    SqList *L = (SqList *)malloc(sizeof(SqList));
    if (L == NULL) {
        // handle allocation failure
        return NULL;
    }

    L->data = (ElemType *)malloc(sizeof(ElemType) * InitSize);
    if (L->data == NULL) {
        // handle allocation failure
        free(L);
        return NULL;
    }
    
    L->MaxSize = InitSize;
    L->length = 0;

    return L;
}

int main() {
SqList *L = InitList(); // allocate on the heap
return 0;
}

The maximal capacity $\texttt{InitSize}$ is fixed at initialization. If requiring more space, a new larger array must be allocated, and the old data copied over.

Singly Linked List

A singly linked list stores each element in a node consisting of two fields:

The list $L$ is accessed via a head pointer $L$ pointing to $a_1$; the last node has $\texttt{next}=\texttt{null}$.

Logical order is preserved solely through the $\texttt{next}$ chain, so nodes may reside anywhere in memory.

Sometimes there is a sentinel node $a_0$ at the head, which does not store data but simplifies insert/delete operations, and can imply the list is empty when $a_0.\texttt{next}=\texttt{null}$.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

typedef struct Node {
    ElemType data;
    struct Node *next;
} Node, *LinkList;

// Initialization with a sentinel node
bool InitListWithSentinel(LinkList *L){
    *L = (Node *)malloc(sizeof(Node));
    if (*L == NULL) return false; // allocation failed
    (*L)->next = NULL; // sentinel node points to null
    return true;
}

// Initialization without a sentinel node
bool InitListWithoutSentinel(LinkList *L){
    *L = NULL; // empty list
    return true;
}

int main() {
LinkList head;
InitListWithSentinel(&head); // or InitListWithoutSentinel(&head)
free(head); // free the sentinel node if used
return 0;
}

• Insert at tail — $O(n)$ (or $O(1)$ if a tail pointer is maintained).
• Delete a given node $p$ — $O(n)$. Must locate the predecessor of $p$ (cannot go backward). If only $p$ is given, copy $p.\texttt{next}$’s data into $p$ and bypass $p.\texttt{next}$ (the lazy deletion trick, not available for the tail) in $O(1)$ time.

For a singly linked list with a sentinel node, it’s empty when $L\texttt{->next}=\texttt{null}$; for one without a sentinel node, it’s empty when $L=\texttt{null}$.

Double Linked List

A doubly linked list augments each node with a backward pointer:

Both forward and backward traversal are supported, there is convenience but also extra space and complexity for implementation.

1
2
3
4

typedef struct DNode {
    ElemType data;
    struct DNode *prev, *next;
} DNode, *DLinkList;

In some cases, there will be another sentinel node at the tail, but we will not discuss it here.

• Insert before/after a given node $p$ — $O(1)$. Adjust $p.\texttt{prev}$ and $p.\texttt{next}$.
• Delete a given node $p$ — $O(1)$. Unlike the singly linked case, the predecessor is immediately available as $p.\texttt{prev}$.

Circular Linked List

A circular linked list replaces the terminal $\texttt{null}$ with a pointer back to the first node, forming a ring. Both singly and doubly linked variants exist.

The last node’s $\texttt{next}$ points to the sentinel if there is one. With sentinel nodes, the list is empty when the sentinel’s $\texttt{next}$ points to itself.

There is a variant of singly circular lists, requiring no sentinel, and maintaining a tail pointer $L$ pointing to the last node instead of the head.

Doubly circular list is similar, and it has properties as follows

• Insert/Delete at head/tail — $O(1)$. The tail pointer allows direct access to the head via $L\texttt{->next}$.
• Insert/Delete at a known node — $O(1)$.

Both singly and doubly circular lists can

• Traversal — starts from any node and stops after one full cycle (requires remembering the starting node or using a sentinel) and singly circular lists can only traverse forward.
• Merge two circular lists — $O(1)$. Swap the $\texttt{next}$ pointers of the two tail nodes.

There are no $\texttt{null}$ checks needed (with a sentinel), uniform code for all positions, natural fit for cyclic data.

Static Linked List

Static linked list stores a linear list in a fixed-size array of nodes

And the head pointer storing no data, only the index of the first node.

1
2
3
4
5

#define MaxSize 50
typedef struct {
    ElemType data;
    int next; // index of the next node
} SLinkList[MaxSize];

$\texttt{node}[0]$ represents the head pointer, and

taking $-1$ to represent $\texttt{null}$.

The array is allocated once and reused, with a free list of available nodes maintained in the same array. This avoids dynamic memory allocation overhead but limits the maximum size of the list.

Hash List

A hash list stores the linear list in a hash table keyed by the integer index $i$:

Collisions are resolved by chaining: each bucket holds a small linked list of $\langle\texttt{index},\texttt{value}\rangle$ pairs. A load factor $\alpha=n/m$ (with $m$ buckets) is kept below a constant threshold; when exceeded, the table is rehashed to a larger $m$.

Operations (average case, simple uniform hashing):

• Access by index $i$ — $O(1)$. Compute $\texttt{Hash}(i)$, walk the chain in that bucket (expected length $\alpha=O(1)$).
• Insert/Delete at index $i$ — $O(1)$. Hash $i$ and add/remove the entry in the bucket.
• Search by value — $O(n)$. Must scan all $n$ entries across all buckets.
• Traversal in order — $O(n+m)$. Either thread an auxiliary linked list through the entries in index order, or extract and sort all indices.

Why use a hash list? It offers $O(1)$ average random access and $O(1)$ average insertion/deletion — combining the best of sequential and linked storage. The price is a larger constant factor (hash computation, collision chains, rehashing) and worst-case $O(n)$ behavior under a poor hash function. It is particularly useful when the index set is sparse (e.g., $n\ll\max\{i\}$) and a sequential array would waste space.

Stack, Queue: Restricted Linear List

Array: Extended Linear List

Set

Tree

Graph

Storage & Implementation

Sequential Storage

Linked Storage

Indexed Storage

Hash Storage

Application

The $n$-th Fibonacci Number

Algorithms

KMP

Exercises

Ex.1.1. Show that the time complexity of the following algorithm is $O(n)$

1
2
3
4

int sum = 0;
for (int i = 1; i < n; i *= 2)
    for (int j = 0; j < i; j++)
        sum++;

Ex.2.1. Given a linear list

try to reverse it with $O(1)$ extra space and $O(m+n)$ time complexity to

Ex.2.2. Given two increasing linear lists

try to find the median of the combined list with $O(\log n)$ time complexity and $O(1)$ extra space.

Ex.2.3. To find the principal number(appear more than $n/2$ times) of a given integer linear list with length $n$ if there exists one in $O(n)$ time complexity and $O(1)$ extra space.

Ex.2.4. Can we realize the deletion of the tail node in a singly linked list in $O(1)$ time with the head pointing to the second last node? Why?

Ex.2.5. Given a singly linked list with a sentinel node, try to reverse it in $O(n)$ time and $O(1)$ extra space.

Ex.2.6. Given two singly linked lists, try to find the first common node of them in $O(m+n)$ time and $O(1)$ extra space.

Ex.2.7. A singly linked list is said to have a cycle if there exists a node $p$ such that $p.\texttt{next}$ points to one of its predecessors. Determine whether a singly linked list has a cycle in $O(n)$ time and $O(1)$ extra space.