Linear structures consist of a finite sequence of elements with identical properties. Common linear data structures include arrays, linked lists, stacks, queues, and strings. While linear structures follow a continuous logical arrangement, their physical storage may be either contiguous or non-contiguous, typically using array-based or pointer-chained formats.

Sequential Lists

Overview and Structure Types

A sequential list stores elements in consecutive physical memory locations, most often implemented with arrays to support insertions, deletions, lookups, and updates.

Two primary variants exist:

1. Fixed-Size Sequential List: Uses a pre-allocated array with a constant length. This approach suffers from inflexibility—underutilizing space if too large, or failing to accommodate growth if too small.

#define MAX_CAPACITY 12
typedef int SElem;

typedef struct FixedSeqList {
    SElem items[MAX_CAPACITY];
    int elem_count;
} FSL;

2. Dynamic Sequential List: Uses heap-allocated memory that resizes dynamically as needed, addressing the fixed-size variant’s limitations.

typedef int DSElem;

typedef struct DynSeqList {
    DSElem* data;
    int used;
    int total_cap;
} DSL;

Core Dynamic Sequential List Operations

We focus on dynamic lists here due to their practical utility. The following code assumes functions are declared in a header and implemented in a source file.

Header Declarations

All modification functions accept a pointer to the DSL struct to modify it in-place.

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int DSElem;

typedef struct DynSeqList {
    DSElem* data;
    int used;
    int total_cap;
} DSL;

// Initialize empty list
void DSLInit(DSL* list);
// Free all allocated memory
void DSLFree(DSL* list);
// Print all elements
void DSLPrint(DSL* list);
// Ensure sufficient capacity
void DSLGrowIfNeeded(DSL* list);

// Add/remove operations
void DSLAppend(DSL* list, DSElem val);
void DSLPrepend(DSL* list, DSElem val);
void DSLRemoveLast(DSL* list);
void DSLRemoveFirst(DSL* list);
void DSLInsertAt(DSL* list, int idx, DSElem val);
void DSLDeleteAt(DSL* list, int idx);

// Lookup and update
int DSLFind(DSL* list, DSElem target);
void DSLModify(DSL* list, int idx, DSElem new_val);

Function Implementations

void DSLInit(DSL* list) {
    assert(list);
    list->data = (DSElem*)malloc(sizeof(DSElem) * 5);
    if (!list->data) {
        perror("DSLInit malloc failed");
        exit(EXIT_FAILURE);
    }
    list->used = 0;
    list->total_cap = 5;
}

void DSLFree(DSL* list) {
    assert(list);
    free(list->data);
    list->data = NULL;
    list->used = 0;
    list->total_cap = 0;
}

void DSLPrint(DSL* list) {
    assert(list);
    for (int i = 0; i < list->used; ++i) {
        printf("%d ", list->data[i]);
    }
    printf("\n");
}

void DSLGrowIfNeeded(DSL* list) {
    assert(list);
    if (list->used == list->total_cap) {
        int new_cap = list->total_cap * 2;
        DSElem* temp = (DSElem*)realloc(list->data, sizeof(DSElem) * new_cap);
        if (!temp) {
            perror("DSLGrowIfNeeded realloc failed");
            exit(EXIT_FAILURE);
        }
        list->data = temp;
        list->total_cap = new_cap;
    }
}

void DSLInsertAt(DSL* list, int idx, DSElem val) {
    assert(list);
    assert(idx >= 0 && idx <= list->used);
    DSLGrowIfNeeded(list);
    for (int j = list->used; j > idx; --j) {
        list->data[j] = list->data[j-1];
    }
    list->data[idx] = val;
    list->used++;
}

void DSLAppend(DSL* list, DSElem val) {
    DSLInsertAt(list, list->used, val);
}

void DSLPrepend(DSL* list, DSElem val) {
    DSLInsertAt(list, 0, val);
}

void DSLDeleteAt(DSL* list, int idx) {
    assert(list);
    assert(idx >= 0 && idx < list->used);
    for (int j = idx; j < list->used - 1; ++j) {
        list->data[j] = list->data[j+1];
    }
    list->used--;
}

void DSLRemoveLast(DSL* list) {
    DSLDeleteAt(list, list->used - 1);
}

void DSLRemoveFirst(DSL* list) {
    DSLDeleteAt(list, 0);
}

int DSLFind(DSL* list, DSElem target) {
    assert(list);
    for (int i = 0; i < list->used; ++i) {
        if (list->data[i] == target) return i;
    }
    return -1;
}

void DSLModify(DSL* list, int idx, DSElem new_val) {
    assert(list);
    assert(idx >= 0 && idx < list->used);
    list->data[idx] = new_val;
}

Common Sequential List Interview Problems

1. Remove All Occurrences of a Value In-Place

Given an array and a value, remove all instances of that value in-place and return the new length. Use O(1) extra space.

int removeElement(int* arr, int arr_size, int val) {
    int write_pos = 0;
    for (int read_pos = 0; read_pos < arr_size; ++read_pos) {
        if (arr[read_pos] != val) {
            arr[write_pos++] = arr[read_pos];
        }
    }
    return write_pos;
}

2. Remove Duplicates from a Sorted Array

Given a non-decreasing sorted array, remove duplicates in-place such that each unique element appears only once, and return the new length.

int removeDuplicates(int* arr, int arr_size) {
    if (arr_size == 0) return 0;
    int unique_pos = 1;
    for (int i = 1; i < arr_size; ++i) {
        if (arr[i] != arr[unique_pos - 1]) {
            arr[unique_pos++] = arr[i];
        }
    }
    return unique_pos;
}

3. Merge Two Sorted Arrays

Merge two sorted arrays nums1 (size m + n, first m elements valid) and nums2 (size n) into nums1 in sorted order.

void merge(int* nums1, int m, int* nums2, int n) {
    int ptr1 = m - 1, ptr2 = n - 1, write_ptr = m + n - 1;
    while (ptr1 >= 0 && ptr2 >= 0) {
        nums1[write_ptr--] = (nums1[ptr1] > nums2[ptr2]) ? nums1[ptr1--] : nums2[ptr2--];
    }
    while (ptr2 >= 0) {
        nums1[write_ptr--] = nums2[ptr2--];
    }
}

Limitations of Sequential Lists

1. Insertions/deletions at the beginning or middle require shifting O(n) elements.
2. Dynamic resizing involves allocating new memory, copying data, and freeing old memory, leading to overhead.
3. Doubling capacity often leaves unused space (e.g., capacity 200 with only 105 elements wastes 95 slots).

Linked Lists

Overview and Classification

Linked lists store elements non-contiguously in memory, using pointers to maintain logical order. Key variants include:

1. Singly Linked List (SLL): Unidirectional traversal, simple structure, often used as a substructure for hash tables or adjacency lists.
2. Doubly Linked Circular List with Sentinel (DLL): Bidirectional traversal, simplifies edge cases, ideal for standalone data storage.

Singly Linked List Implementation

We first implement a non-circular, headless singly linked list.

Header Declarations

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int SLLVal;

typedef struct SLLNode {
    SLLVal value;
    struct SLLNode* next;
} SLLNode;

// Create a new node
SLLNode* SLLCreateNode(SLLVal val);
// Print the list
void SLLPrint(SLLNode* head);
// Free all nodes
void SLLFree(SLLNode** head_ptr);

// Add/remove operations
void SLLPushFront(SLLNode** head_ptr, SLLVal val);
void SLLPushBack(SLLNode** head_ptr, SLLVal val);
void SLLPopFront(SLLNode** head_ptr);
void SLLPopBack(SLLNode** head_ptr);

// Lookup and modify
SLLNode* SLLFind(SLLNode* head, SLLVal target);
void SLLInsertBefore(SLLNode** head_ptr, SLLNode* pos, SLLVal val);
void SLLInsertAfter(SLLNode* pos, SLLVal val);
void SLLErase(SLLNode** head_ptr, SLLNode* pos);
void SLLEraseAfter(SLLNode* pos);

Function Implementations

SLLNode* SLLCreateNode(SLLVal val) {
    SLLNode* new_node = (SLLNode*)malloc(sizeof(SLLNode));
    if (!new_node) {
        perror("SLLCreateNode malloc failed");
        exit(EXIT_FAILURE);
    }
    new_node->value = val;
    new_node->next = NULL;
    return new_node;
}

void SLLPrint(SLLNode* head) {
    SLLNode* current = head;
    while (current) {
        printf("%d -> ", current->value);
        current = current->next;
    }
    printf("NULL\n");
}

void SLLPushFront(SLLNode** head_ptr, SLLVal val) {
    assert(head_ptr);
    SLLNode* new_node = SLLCreateNode(val);
    new_node->next = *head_ptr;
    *head_ptr = new_node;
}

void SLLPushBack(SLLNode** head_ptr, SLLVal val) {
    assert(head_ptr);
    SLLNode* new_node = SLLCreateNode(val);
    if (!*head_ptr) {
        *head_ptr = new_node;
        return;
    }
    SLLNode* tail = *head_ptr;
    while (tail->next) {
        tail = tail->next;
    }
    tail->next = new_node;
}

void SLLPopFront(SLLNode** head_ptr) {
    assert(head_ptr && *head_ptr);
    SLLNode* temp = *head_ptr;
    *head_ptr = (*head_ptr)->next;
    free(temp);
}

void SLLPopBack(SLLNode** head_ptr) {
    assert(head_ptr && *head_ptr);
    if (!(*head_ptr)->next) {
        free(*head_ptr);
        *head_ptr = NULL;
        return;
    }
    SLLNode* second_last = *head_ptr;
    while (second_last->next->next) {
        second_last = second_last->next;
    }
    free(second_last->next);
    second_last->next = NULL;
}

SLLNode* SLLFind(SLLNode* head, SLLVal target) {
    SLLNode* current = head;
    while (current) {
        if (current->value == target) return current;
        current = current->next;
    }
    return NULL;
}

void SLLInsertAfter(SLLNode* pos, SLLVal val) {
    assert(pos);
    SLLNode* new_node = SLLCreateNode(val);
    new_node->next = pos->next;
    pos->next = new_node;
}

void SLLInsertBefore(SLLNode** head_ptr, SLLNode* pos, SLLVal val) {
    assert(head_ptr && pos);
    if (pos == *head_ptr) {
        SLLPushFront(head_ptr, val);
        return;
    }
    SLLNode* prev = *head_ptr;
    while (prev && prev->next != pos) {
        prev = prev->next;
    }
    assert(prev); // pos not found in list
    SLLInsertAfter(prev, val);
}

void SLLEraseAfter(SLLNode* pos) {
    assert(pos && pos->next);
    SLLNode* temp = pos->next;
    pos->next = temp->next;
    free(temp);
}

void SLLErase(SLLNode** head_ptr, SLLNode* pos) {
    assert(head_ptr && pos);
    if (pos == *head_ptr) {
        SLLPopFront(head_ptr);
        return;
    }
    SLLNode* prev = *head_ptr;
    while (prev && prev->next != pos) {
        prev = prev->next;
    }
    assert(prev); // pos not found
    SLLEraseAfter(prev);
}

void SLLFree(SLLNode** head_ptr) {
    assert(head_ptr);
    SLLNode* current = *head_ptr;
    while (current) {
        SLLNode* next_node = current->next;
        free(current);
        current = next_node;
    }
    *head_ptr = NULL;
}

Common Singly Linked List Interview Problems

1. Remove All Occurrences of a Value

Remove all nodes with a given value from a singly linked list and return the new head.

struct ListNode* removeElements(struct ListNode* head, int val) {
    struct ListNode dummy;
    dummy.next = head;
    struct ListNode* prev = &dummy;
    struct ListNode* current = head;
    while (current) {
        if (current->val == val) {
            prev->next = current->next;
            free(current);
            current = prev->next;
        } else {
            prev = current;
            current = current->next;
        }
    }
    return dummy.next;
}

2. Find the Middle Node

Return the middle node of a linked list. If even, return the second middle node.

struct ListNode* middleNode(struct ListNode* head) {
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

3. Reverse a Linked List

Reverse a singly linked list and return the new head.

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* reversed = NULL;
    struct ListNode* current = head;
    while (current) {
        struct ListNode* next_temp = current->next;
        current->next = reversed;
        reversed = current;
        current = next_temp;
    }
    return reversed;
}

Doubly Linked Circular List with Sentinel Implementation

This variant uses a sentinel (dummy) node to eliminate edge cases for empty lists, head/tail operations.

Header Declarations

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

typedef int DLLVal;

typedef struct DLLNode {
    DLLVal data;
    struct DLLNode* prev;
    struct DLLNode* next;
} DLLNode;

// Initialize sentinel node
DLLNode* DLLInit(void);
// Check if list is empty (only sentinel)
bool DLLIsEmpty(DLLNode* sentinel);
// Print list
void DLLPrint(DLLNode* sentinel);
// Free all nodes including sentinel
void DLLFree(DLLNode* sentinel);

// Add/remove operations
void DLLPushBack(DLLNode* sentinel, DLLVal val);
void DLLPushFront(DLLNode* sentinel, DLLVal val);
void DLLPopBack(DLLNode* sentinel);
void DLLPopFront(DLLNode* sentinel);
void DLLInsertBefore(DLLNode* pos, DLLVal val);
void DLLErase(DLLNode* pos);

// Lookup
DLLNode* DLLFind(DLLNode* sentinel, DLLVal target);

Function Implementations

DLLNode* DLLCreateNode(DLLVal val) {
    DLLNode* new_node = (DLLNode*)malloc(sizeof(DLLNode));
    if (!new_node) {
        perror("DLLCreateNode malloc failed");
        exit(EXIT_FAILURE);
    }
    new_node->data = val;
    new_node->prev = new_node->next = NULL;
    return new_node;
}

DLLNode* DLLInit(void) {
    DLLNode* sentinel = DLLCreateNode(-999); // Dummy value
    sentinel->prev = sentinel;
    sentinel->next = sentinel;
    return sentinel;
}

bool DLLIsEmpty(DLLNode* sentinel) {
    assert(sentinel);
    return sentinel->next == sentinel;
}

void DLLPrint(DLLNode* sentinel) {
    assert(sentinel);
    printf("Sentinel <=> ");
    DLLNode* current = sentinel->next;
    while (current != sentinel) {
        printf("%d <=> ", current->data);
        current = current->next;
    }
    printf("Sentinel\n");
}

void DLLInsertBefore(DLLNode* pos, DLLVal val) {
    assert(pos);
    DLLNode* new_node = DLLCreateNode(val);
    DLLNode* pos_prev = pos->prev;
    new_node->prev = pos_prev;
    new_node->next = pos;
    pos_prev->next = new_node;
    pos->prev = new_node;
}

void DLLPushBack(DLLNode* sentinel, DLLVal val) {
    DLLInsertBefore(sentinel, val);
}

void DLLPushFront(DLLNode* sentinel, DLLVal val) {
    DLLInsertBefore(sentinel->next, val);
}

void DLLErase(DLLNode* pos) {
    assert(pos && pos->prev != pos); // Cannot erase sentinel
    DLLNode* pos_prev = pos->prev;
    DLLNode* pos_next = pos->next;
    pos_prev->next = pos_next;
    pos_next->prev = pos_prev;
    free(pos);
}

void DLLPopBack(DLLNode* sentinel) {
    assert(sentinel && !DLLIsEmpty(sentinel));
    DLLErase(sentinel->prev);
}

void DLLPopFront(DLLNode* sentinel) {
    assert(sentinel && !DLLIsEmpty(sentinel));
    DLLErase(sentinel->next);
}

DLLNode* DLLFind(DLLNode* sentinel, DLLVal target) {
    assert(sentinel);
    DLLNode* current = sentinel->next;
    while (current != sentinel) {
        if (current->data == target) return current;
        current = current->next;
    }
    return NULL;
}

void DLLFree(DLLNode* sentinel) {
    assert(sentinel);
    DLLNode* current = sentinel->next;
    while (current != sentinel) {
        DLLNode* next_node = current->next;
        free(current);
        current = next_node;
    }
    free(sentinel);
}

Comparison Between Sequential Lists and Linked Lists

Aspect	Sequential List	Linked List
Physical Storage	Contiguous memory blocks	Non-contiguous, pointer-linked
Random Access	O(1) via index	O(n) traversal required
Insert/Delete Middle	O(n) element shifts	O(1) pointer modifications (if pos known)
Capacity Management	Requires resizing (overhead + waste)	No fixed capacity, no waste
Cache Locality	Excellent (high cache hit rate)	Poor (low cacche hit rate)
Use Case	Frequent lookups, stable element count	Frequent insertions/deletions anywhere