手写链表实操代码

单链表

#include <iostream>
using namespace std;

// 节点定义
struct SNode {
    int data;
    SNode* next;
    SNode(int val) : data(val), next(nullptr) {}
};

// 初始化（创建头结点）
SNode* initList() {
    SNode* head = new SNode(0); // 头结点不存数据
    head->next = nullptr;
    return head;
}

// 遍历打印
void traverse(SNode* head) {
    SNode* p = head->next;
    while (p) {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

// 头插
void insertHead(SNode* head, int val) {
    SNode* newNode = new SNode(val);
    newNode->next = head->next;
    head->next = newNode;
}

// 尾插
void insertTail(SNode* head, int val) {
    SNode* newNode = new SNode(val);
    SNode* p = head;
    while (p->next) p = p->next;
    p->next = newNode;
}

// 指定位置插入（位置从1开始，在pos位置前插入）
bool insertPos(SNode* head, int pos, int val) {
    if (pos < 1) return false;
    SNode* p = head;
    for (int i = 1; i < pos; ++i) {
        if (!p->next) return false; // 位置超出链表长度
        p = p->next;
    }
    SNode* newNode = new SNode(val);
    newNode->next = p->next;
    p->next = newNode;
    return true;
}

// 头删
bool deleteHead(SNode* head) {
    if (!head->next) return false;
    SNode* del = head->next;
    head->next = del->next;
    delete del;
    return true;
}

// 尾删
bool deleteTail(SNode* head) {
    if (!head->next) return false;
    SNode* p = head;
    while (p->next && p->next->next) p = p->next;
    SNode* del = p->next;
    p->next = nullptr;
    delete del;
    return true;
}

// 按值删除第一个匹配节点
bool deleteByValue(SNode* head, int val) {
    SNode* p = head;
    while (p->next && p->next->data != val) p = p->next;
    if (!p->next) return false;
    SNode* del = p->next;
    p->next = del->next;
    delete del;
    return true;
}

双链表（带头结点）

#include <iostream>
using namespace std;

// 节点定义
struct DNode {
    int data;
    DNode* prev;
    DNode* next;
    DNode(int val) : data(val), prev(nullptr), next(nullptr) {}
};

// 初始化
DNode* initList() {
    DNode* head = new DNode(0);
    head->prev = head->next = nullptr;
    return head;
}

// 遍历（正向）
void traverse(DNode* head) {
    DNode* p = head->next;
    while (p) {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

// 头插
void insertHead(DNode* head, int val) {
    DNode* newNode = new DNode(val);
    newNode->next = head->next;
    if (head->next) head->next->prev = newNode;
    head->next = newNode;
    newNode->prev = head;
}

// 尾插
void insertTail(DNode* head, int val) {
    DNode* newNode = new DNode(val);
    DNode* p = head;
    while (p->next) p = p->next;
    p->next = newNode;
    newNode->prev = p;
}

// 指定位置插入（位置从1开始）
bool insertPos(DNode* head, int pos, int val) {
    if (pos < 1) return false;
    DNode* p = head;
    for (int i = 1; i < pos; ++i) {
        if (!p->next) return false;
        p = p->next;
    }
    DNode* newNode = new DNode(val);
    newNode->next = p->next;
    if (p->next) p->next->prev = newNode;
    p->next = newNode;
    newNode->prev = p;
    return true;
}

// 头删
bool deleteHead(DNode* head) {
    if (!head->next) return false;
    DNode* del = head->next;
    head->next = del->next;
    if (del->next) del->next->prev = head;
    delete del;
    return true;
}

// 尾删
bool deleteTail(DNode* head) {
    if (!head->next) return false;
    DNode* p = head;
    while (p->next) p = p->next;
    DNode* del = p;
    p->prev->next = nullptr;
    delete del;
    return true;
}

// 按值删除第一个匹配节点
bool deleteByValue(DNode* head, int val) {
    DNode* p = head->next;
    while (p && p->data != val) p = p->next;
    if (!p) return false;
    p->prev->next = p->next;
    if (p->next) p->next->prev = p->prev;
    delete p;
    return true;
}

单循环链表（带头结点，尾next指向头结点）

#include <iostream>
using namespace std;

struct CSNode {
    int data;
    CSNode* next;
    CSNode(int val) : data(val), next(nullptr) {}
};

// 初始化：头结点自己循环
CSNode* initList() {
    CSNode* head = new CSNode(0);
    head->next = head;   // 空链表时头结点指向自身
    return head;
}

// 遍历（需注意结束条件，因为无NULL）
void traverse(CSNode* head) {
    if (head->next == head) {
        cout << "Empty" << endl;
        return;
    }
    CSNode* p = head->next;
    while (p != head) {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

// 头插
void insertHead(CSNode* head, int val) {
    CSNode* newNode = new CSNode(val);
    newNode->next = head->next;
    head->next = newNode;
}

// 尾插（需要找到尾节点，即pre=head的节点）
void insertTail(CSNode* head, int val) {
    CSNode* newNode = new CSNode(val);
    CSNode* p = head;
    while (p->next != head) p = p->next;
    p->next = newNode;
    newNode->next = head;
}

// 指定位置插入（位置从1开始，在pos前插入）
bool insertPos(CSNode* head, int pos, int val) {
    if (pos < 1) return false;
    CSNode* p = head;
    for (int i = 1; i < pos; ++i) {
        p = p->next;
        if (p == head) return false; // 超出长度（循环链表需注意）
    }
    CSNode* newNode = new CSNode(val);
    newNode->next = p->next;
    p->next = newNode;
    return true;
}

// 头删
bool deleteHead(CSNode* head) {
    if (head->next == head) return false;
    CSNode* del = head->next;
    head->next = del->next;
    delete del;
    return true;
}

// 尾删
bool deleteTail(CSNode* head) {
    if (head->next == head) return false;
    CSNode* p = head;
    while (p->next->next != head) p = p->next;
    CSNode* del = p->next;
    p->next = head;
    delete del;
    return true;
}

// 按值删除第一个匹配节点（注意循环链表中不能删头结点）
bool deleteByValue(CSNode* head, int val) {
    if (head->next == head) return false;
    CSNode* p = head;
    while (p->next != head && p->next->data != val) p = p->next;
    if (p->next == head) return false;
    CSNode* del = p->next;
    p->next = del->next;
    delete del;
    return true;
}

双循环链表（带头结点，prev和next均循环）

#include <iostream>
using namespace std;

struct CDNode {
    int data;
    CDNode* prev;
    CDNode* next;
    CDNode(int val) : data(val), prev(nullptr), next(nullptr) {}
};

// 初始化：头结点自己双向循环
CDNode* initList() {
    CDNode* head = new CDNode(0);
    head->prev = head;
    head->next = head;
    return head;
}

// 遍历（正向）
void traverse(CDNode* head) {
    if (head->next == head) {
        cout << "Empty" << endl;
        return;
    }
    CDNode* p = head->next;
    while (p != head) {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

// 头插
void insertHead(CDNode* head, int val) {
    CDNode* newNode = new CDNode(val);
    newNode->next = head->next;
    newNode->prev = head;
    head->next->prev = newNode;
    head->next = newNode;
}

// 尾插（即头结点的前驱处插入）
void insertTail(CDNode* head, int val) {
    CDNode* newNode = new CDNode(val);
    CDNode* tail = head->prev;
    tail->next = newNode;
    newNode->prev = tail;
    newNode->next = head;
    head->prev = newNode;
}

// 指定位置插入（位置从1开始）
bool insertPos(CDNode* head, int pos, int val) {
    if (pos < 1) return false;
    CDNode* p = head;
    for (int i = 1; i < pos; ++i) {
        p = p->next;
        if (p == head) return false;
    }
    CDNode* newNode = new CDNode(val);
    newNode->next = p->next;
    newNode->prev = p;
    p->next->prev = newNode;
    p->next = newNode;
    return true;
}

// 头删
bool deleteHead(CDNode* head) {
    if (head->next == head) return false;
    CDNode* del = head->next;
    head->next = del->next;
    del->next->prev = head;
    delete del;
    return true;
}

// 尾删
bool deleteTail(CDNode* head) {
    if (head->next == head) return false;
    CDNode* del = head->prev;
    head->prev = del->prev;
    del->prev->next = head;
    delete del;
    return true;
}

// 按值删除第一个匹配节点
bool deleteByValue(CDNode* head, int val) {
    if (head->next == head) return false;
    CDNode* p = head->next;
    while (p != head && p->data != val) p = p->next;
    if (p == head) return false;
    p->prev->next = p->next;
    p->next->prev = p->prev;
    delete p;
    return true;
}