Understanding Linked Lists: Types, Core Concepts, and a Complete C Implementation

Linked lists are a fundamental data structure; this tutorial divides them into five categories: (1) singly linked list without a head node, (2) singly linked list with a head node, (3) doubly linked list without a head node, (4) doubly linked list with a head node, and (5) doubly circular linked list with a head node.

Basic Concepts

Head pointer: The pointer that references the first node (or the head node if one exists). It uniquely identifies the list and is never NULL, even when the list is empty.

Head node: An optional dummy node placed before the first real element; its data field is usually unused (sometimes stores list length). It simplifies insertion and deletion at the beginning of the list.

Difference Between Singly and Doubly Linked Lists

A singly linked list node contains only a pointer to the next node, making backward traversal impossible. A doubly linked list node contains both next and previous pointers, allowing fast access to the preceding node.

In practice, the most frequently used structure is the doubly circular linked list with a head node.

Doubly Circular Linked List Demo (C)

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

typedef struct node {
    int data;               // data field
    struct node *next;      // pointer to next node
    struct node *prev;      // pointer to previous node
} Node;

// Create the list head (circular)
Node* creatList() {
    Node *HeadNode = (Node *)malloc(sizeof(Node));
    HeadNode->next = HeadNode->prev = HeadNode; // points to itself
    return HeadNode;
}

// Create a new node with given data
Node* creatNode(int data) {
    Node* newNode = (Node *)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    newNode->prev = NULL;
    return newNode;
}

// Traverse and print the list (forward)
void printList(Node *headNode) {
    Node *p = headNode->next;
    while(p != headNode) {
        printf("%d\t", p->data);
        p = p->next;
    }
    printf("\n");
}

// Insert a node at the head (after the dummy head)
void insertNodebyHead(Node *headNode, int data) {
    Node *newNode = creatNode(data);
    newNode->prev = headNode;
    newNode->next = headNode->next;
    headNode->next->prev = newNode;
    headNode->next = newNode;
}

// Insert a node at the tail (before the dummy head)
void insertNodebyTail(Node *headNode, int data) {
    Node *newNode = creatNode(data);
    Node *lastNode = headNode;
    while(lastNode->next != headNode) {
        lastNode = lastNode->next;
    }
    newNode->next = headNode;
    newNode->prev = lastNode;
    lastNode->next = newNode;
    headNode->prev = newNode;
}

// Delete a node by its data value
void deleteNodebyAppoin(Node *headNode, int posData) {
    Node *posNode = headNode->next;
    Node *posNodeFront = headNode;
    if(posNode == NULL) {
        printf("链表为空，无法删除");
        return;
    }
    while(posNode->data != posData) {
        posNodeFront = posNode;
        posNode = posNodeFront->next;
        if(posNode->next == headNode) {
            printf("没有找到，无法删除");
            return;
        }
    }
    posNodeFront->next = posNode->next;
    posNode->next->prev = posNodeFront;
    free(posNode);
}

int main() {
    Node* List = creatList();
    insertNodebyHead(List, 1);
    insertNodebyHead(List, 2);
    insertNodebyHead(List, 3);
    printList(List);
    insertNodebyTail(List, 0);
    printList(List);
    deleteNodebyAppoin(List, 2);
    printList(List);
    return 0;
}

The result of running the program demonstrates that creation, traversal, head insertion, tail insertion, and deletion for a doubly circular linked list follow the same principles as a singly linked list, with additional pointer adjustments for the previous links.

For readers who find certain steps confusing, the author has added detailed comments and accompanying diagrams to aid understanding.