Linear Lists

A linear list is a finite sequence of n data elements sharing the same characteristics. It serves as a widely used data structure in practice, with common implementations including sequential lists, linked lists, stacks, queues, and strings.

Logically, a linear list maintains a linear structure resembling a continuous line. However, its physical storage in memory may not be contiguous. Linear lists are typically stored using either array-based or linked-node structures.

Sequential List Implementation

Structure and Concepts

A sequential list employs a contiguous block of memory to store data elements in sequence, typically implemented using arrays. Operations like insertion, deletion, search, and modification are performed on this array structure.

Sequential lists can be categorized as:

• Static Sequential List: Uses a fixed-size array for element storage
• Dynamic Sequential List: Utilizes a dynamically allocated array

Dynamic Sequential List Interface

Static sequential lists are only suitable when the exact data quantity is known in advance. Their fixed-size arrays can lead to either wasted space or insufficient capacity. Dynamic sequential lists address this by allocating memory as needed.

typedef int DataType;

typedef struct DynamicArray {
    DataType* elements;  // Pointer to dynamic array
    size_t count;        // Number of valid elements
    size_t capacity;     // Total capacity
} DynamicArray;

// Core operation interfaces
void InitArray(DynamicArray* arr);
void CheckCapacity(DynamicArray* arr);
void AppendElement(DynamicArray* arr, DataType value);
void RemoveLast(DynamicArray* arr);
void PrependElement(DynamicArray* arr, DataType value);
void RemoveFirst(DynamicArray* arr);
int FindElement(DynamicArray* arr, DataType value);
void InsertAt(DynamicArray* arr, size_t position, DataType value);
void DeleteAt(DynamicArray* arr, size_t position);
void DestroyArray(DynamicArray* arr);
void PrintArray(DynamicArray* arr);

Common Array Problems

1. Remove all occurrences of a specific value from an array with O(N) time and O(1) space complexity
2. Remove duplicates from a sorted array
3. Merge two sorted arrays

Limitations and Considerations

Issues:

• Insertion/deletion at middle or beginning positions requires O(N) time complexity
• Capacity expansion involves memory allocation, data copying, and deallocation overhead
• Typical doubling strategy for capacity growth may lead to space wastage

Linked List Implementation

Basic Concepts

A linked list is a non-contiguous storage structure where data elements are logically ordered through pointer linkages between nodes.

Classification Variations

Linked lists can be categorized by three characteristics:

• Singly vs Doubly Linked
• With vs Without Head Node
• Circular vs Linear

Combining these gives eight possible structures, but two are most common:

1. Singly Linked Linear List: Simple structure, often used as substructure in hash tables and graph adjacency lists
2. Doubly Linked Circular List with Head: Complex structure offering implementation advantages for standalone data storage

Singly Linked List Implementation

typedef int NodeValue;

typedef struct ListNode {
    NodeValue value;
    struct ListNode* next;
} ListNode;

ListNode* CreateNode(NodeValue val);
void PrintList(ListNode* head);
void AppendNode(ListNode** headRef, NodeValue val);
void PrependNode(ListNode** headRef, NodeValue val);
void RemoveLastNode(ListNode** headRef);
void RemoveFirstNode(ListNode** headRef);
ListNode* FindNode(ListNode* head, NodeValue val);
void InsertAfter(ListNode* position, NodeValue val);
void DeleteAfter(ListNode* position);

Common Linked List Problems

1. Remove all nodes containing a specific value
2. Reverse a linked list
3. Find the middle node of a linked list
4. Find the k-th node from the end
5. Merge two sorted linked lists
6. Partition list around a pivot value
7. Check for palindrome structure
8. Find intersection node of two lists
9. Detect cycle in a linked list
10. Find cycle entry point
11. Copy list with random pointers

Cycle Detection Example

bool HasCycle(struct ListNode* head) {
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        
        if (slow == fast) {
            return true;
        }
    }
    return false;
}

Doubly Linked List Interface

typedef int ListData;

typedef struct DListNode {
    ListData data;
    struct DListNode* next;
    struct DListNode* prev;
} DListNode;

DListNode* CreateList();
void DestroyList(DListNode* head);
void PrintList(DListNode* head);
void AppendNode(DListNode* head, ListData x);
void RemoveLast(DListNode* head);
void PrependNode(DListNode* head, ListData x);
void RemoveFirst(DListNode* head);
DListNode* FindNode(DListNode* head, ListData x);
void InsertBefore(DListNode* position, ListData x);
void DeleteNode(DListNode* position);

Comparison of Sequential and Linked Lists

Sequential lists offer fast random access but suffer from fixed pre-allocated space limitations and inefficient insertions/deletions. Linked lists provide dynamic memory allocation and efficient modifications but lack direct random access capabilities. The choice between them depends on specific application requirements including data volume, operation frequency, and performance characteristics.