愿你坚持不懈,努力进步,进阶成自己理想的人

—— 2017.09, 写给3年后的自己

链表总结

链表是一种常用的数据结构,相比数组,它的优点是可以不用固定长度,不用预先分配一段连续的内存空
间,因此它的空间利用率比较高。然而数组的优点,也是它的缺点,数组的检索操作可以在O(1)时间内
完成,而链表往往需要O(n)时间

链表的节点

实现一个链表,首先需要定义链表的节点结构体,用于保存数据和与其他节点的关联指针。对于单链表而言,节点可以这么写:

struct Node {
    int value;
    Node* next;
}

next是一个Node指针类型的成员变量,用于指向当前节点的下一个节点,因为节点之间的这种关系像是链条一般,故得名“链表”

链表可以这么形象化表示:[ 1 ]->[ 3 ]->[ 2 ]->[ 4 ]->NULL

链表的添加操作

单链表的添加,需要先进行遍历,然后再插入节点,这里以向尾部添加节点操作为例。向尾部添加节点,由于链表内存空间不连续,所以我们需要通过遍历找到链表当前的末节点,才能实行节点添加操作:
用例:

  • 空链表时:
    节点添加前:NULL
    节点添加后:[ newNode ]->NULL
    新节点就成为了头节点
  • 非空链表:
    节点添加前:[ ]->[ ]->[ ]->NULL
    节点添加后:[ ]->[ ]->[ ]->[ newNode ]->NULL
    之前的末节点的next指向新节点,新节点的next指向NULL
void push(Node** head, int value) {
    Node* newNode = new Node();
    newNode->value = value;
    newNode->next  = NULL;
    if(*head == NULL) {
        *head = newNode;
    } else {
        Node* temp = *head;
        while(temp) {
            temp = temp->next;
        }
        temp->next = newNode;
    }
}

链表的删除操作

单链表的删除操作,关键在于找出要删除节点的前一个节点,然后将其next指向要删除节点的下一节点,并最后释放要删除节点所占据的内存空间即可。这里实现一个删除指定的数值的操作(仅删除数值第一次出现的节点),
用例:

  • 1、链表头指针为空:返回
  • 2、链表只有一个节点,且等于被删数值:
    删除前:[ 1 ]->NULL
    删除后:NULL
    释放该节点空间并且头节点指向NULL即可,也可以换个说法,让头节点指向当前头节点的下一个节点(NULL),并删除原来的头节点即可
  • 3、链表只有一个节点,且不等于被删除数值:不变
  • 4、删除链表头部的节点:
    删除前:[ 1 ]->[ 3 ]->[ 4 ]->NULL
    删除后:[ 3 ]->[ 4 ]->NULL
    让头节点指向当前头节点的下一个节点(3),并删除原来的头节点即可
    可以发现,用例2、4是可以统一为一个操作的
  • 5、删除链表中间的节点:
    删除前:[ 1 ]->[ 3 ]->[ 4 ]->NULL
    删除后:[ 1 ]->[ 4 ]->NULL
    找到[ 3 ]的前一个节点[ 1 ],将[ 1 ]的next指向[ 3 ]的next(为4),并释放[ 3 ]即可
  • 6、删除链表末尾的节点:
    删除前:[ 1 ]->[ 3 ]->[ 4 ]->NULL
    删除后:[ 1 ]->[ 3 ]->NULL
    找到[ 4 ]的前一个节点[ 3 ],将[ 3 ]的next指向[ 4 ]的next(为NULL),并释放[ 4 ]即可
    可以发现,用例5、6是可以统一为一个操作的
void remove(Node** head, int value) {
    if(head == NULL || *head == NULL) return;
    Node* nodeToDelete = NULL;

    if((*head)->value == value) {
        nodeToDelete = (*head);
        *head = (*head)->next;
    } else {
        Node* temp = *head;
        Node* pre = NULL;
        while(temp) {
            if(temp->value == value) {
                nodeToDelete = temp;
                pre->next = temp->next;
                break;
            }
            pre = temp;
            temp = temp->next
        }
    }

    if(nodeToDelete != NULL) delete nodeToDelete;
}

链表的打印操作

1、正序打印

void print(Node** head) {
    if(head == NULL || *head == NULL) return;

    Node* temp = *head;
    while(temp) {
        cout << temp->value << endl;
        temp = temp->next;
    }
}

2、逆序打印

void invertPrint(Node** head) {
    if(head == NULL || *head == NULL) return;

    stack<Node*> s;
    Node* temp = *head;
    while(temp) {
        s.push(temp);
        temp = temp->next;
    }
    while(!s.empty()) {
        cout << s.top()->value << endl;
        s.pop();
    }
}