Understanding Linked Lists in C Language

1. Significance and Function of Linked Lists

Significance:

Linked lists provide the capability for dynamic memory management, allowing the creation and release of data elements as needed during program execution, thus overcoming the limitations of arrays that require a predetermined size.

Main Functions:

• Dynamic Memory Allocation: No need to know the size of the data in advance

• Efficient Insertion and Deletion: The time complexity for inserting and deleting elements at any position is O(1)

• High Memory Utilization: Allocated as needed, avoiding memory waste

• Flexibility: Easily reorganize data relationships

2. Basic Structure of Linked Lists

// Definition of linked list node
struct ListNode {
    int data;              // Data field
    struct ListNode *next; // Pointer field, pointing to the next node
};
typedef struct ListNode ListNode;

3. Types of Linked Lists

Single Linked List

typedef struct Node {
    int data;
    struct Node *next;
} Node;

Doubly Linked List

typedef struct DNode {
    int data;
    struct DNode *prev;    // Pointer to the previous node
    struct DNode *next;    // Pointer to the next node
} DNode;

Circular Linked List

// The next of the tail node points to the head node
typedef struct CNode {
    int data;
    struct CNode *next;
} CNode;

4. Common Operation Examples

Creating a Node

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        return NULL;
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

Inserting a Node

// Insert at the head of the linked list
void insertAtHead(Node** head, int data) {
    Node* newNode = createNode(data);
    newNode->next = *head;
    *head = newNode;
}
// Insert at the tail of the linked list
void insertAtTail(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    Node* temp = *head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
}

Deleting a Node

void deleteNode(Node** head, int key) {
    Node* temp = *head;
    Node* prev = NULL;
    // If the node to be deleted is the head node
    if (temp != NULL && temp->data == key) {
        *head = temp->next;
        free(temp);
        return;
    }
    // Search for the node to be deleted
    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }
    if (temp == NULL) return; // Not found
    prev->next = temp->next;
    free(temp);
}

Traversing the Linked List

void printList(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

5. Use Cases for Linked Lists

Scenarios Suitable for Using Linked Lists:

1. Uncertain Data Volume: Situations where data needs to be dynamically added or removed

2. Frequent Insertions and Deletions: Frequent insertions and deletions in the middle of a sequence

3. Implementing Other Data Structures: Stacks, queues, graphs, hash tables, etc.

4. Memory-Constrained Environments: Unable to pre-allocate large contiguous memory

5. Need for Flexible Reorganization: Frequently need to reorganize data relationships

Specific Application Examples:

Implementing a Stack

typedef struct Stack {
    Node* top;
} Stack;
void push(Stack* stack, int data) {
    Node* newNode = createNode(data);
    newNode->next = stack->top;
    stack->top = newNode;
}
int pop(Stack* stack) {
    if (stack->top == NULL) return -1;
    Node* temp = stack->top;
    int data = temp->data;
    stack->top = stack->top->next;
    free(temp);
    return data;
}

Implementing a Queue

typedef struct Queue {
    Node* front;
    Node* rear;
} Queue;
void enqueue(Queue* queue, int data) {
    Node* newNode = createNode(data);
    if (queue->rear == NULL) {
        queue->front = queue->rear = newNode;
        return;
    }
    queue->rear->next = newNode;
    queue->rear = newNode;
}
int dequeue(Queue* queue) {
    if (queue->front == NULL) return -1;
    Node* temp = queue->front;
    int data = temp->data;
    queue->front = queue->front->next;
    if (queue->front == NULL) queue->rear = NULL;
    free(temp);
    return data;
}

Student Management System

typedef struct Student {
    int id;
    char name[50];
    float score;
    struct Student* next;
} Student;
// Adding student information
void addStudent(Student** head, int id, char* name, float score) {
    Student* newStudent = (Student*)malloc(sizeof(Student));
    newStudent->id = id;
    strcpy(newStudent->name, name);
    newStudent->score = score;
    newStudent->next = *head;
    *head = newStudent;
}

6. Linked List vs Array

Characteristics	Array	Linked List
Memory Allocation	Static Continuous	Dynamic Non-continuous
Size	Fixed	Can be Dynamically Adjusted
Insertion/Deletion	O(n)	O(1)
Random Access	O(1)	O(n)
Memory Efficiency	May Waste	Allocated as Needed
Cache Friendly	Yes	No

7. Summary of Advantages and Disadvantages

Advantages:

• ✅ Dynamic size, flexible expansion

• ✅ Efficient insertion and deletion

• ✅ High memory utilization

• ✅ Easy to implement complex data structures

Disadvantages:

• ❌ Does not support random access

• ❌ Requires extra memory to store pointers

• ❌ Not cache friendly

• ❌ Relatively complex to implement

Linked lists are a very important basic data structure in C language, and mastering linked lists is crucial for understanding more complex data structures and algorithms. In practical programming, it is necessary to choose the appropriate data structure based on specific needs.