跳至主要內容

链表基础知识

张威大约 5 分钟数据结构与算法基础知识链表

链表基础知识

特点：每一个节点都是在堆内存上独立new出来的，节点内存不连续

  • 优点
    • 内存利用率高，不需要大块连续内存
    • 插入和删除节点不需要移动其它节点，时间复杂度O(1)
    • 不需要专门进行扩容操作
  • 缺点
    • 内存占用量大，每一个节点多出存放地址的空间
    • 节点内存不连续，无法进行内存随机访问
    • 链表搜索效率不高，只能从头节点开始逐节点遍历

单向链表

特点：

  • 每一个节点除了数据域，还有一个next指针域指向下一个节点(存储了下一个节点的地址)，但是无法回退到前一个节点

  • 末尾节点的指针域是NULL

单向链表的实现

//LinkedList.h
#ifndef _LINKEDLIST_H_
#define _LINKEDLIST_H_

#include <iostream>

using std::cout;
using std::endl;

class LinkedList {
public:
    LinkedList();
    ~LinkedList();
    void push_back(int val);
    void pop_back();
    void push_front(int val);
    void pop_front();
    void remove(int val);
    void removeAll(int val);
    bool find(int val);
    void show();


private:
    struct Node{
        int _data;
        Node* _next;
        Node(int data = 0, Node* next = nullptr) : _data(data), _next(next) {}
    };
    
    Node* head;
};


#endif // _LINKEDLIST_H_

//LinkedList.cc
#include "LinkedList.h"        

LinkedList::LinkedList() {
    head = new Node();    
}

LinkedList::~LinkedList() {
    Node* p = head;
    while(p != nullptr) {
        head = head->_next;
        delete p;
        p = head;
    }
}

void LinkedList::push_back(int val) {
    Node* newNode = new Node(val);
    Node* p = head;
    while(p->_next != nullptr) {
        p = p->_next;
    }
    p->_next = newNode;
}

void LinkedList::pop_back() {
    Node* cur = head->_next;
    Node* pre = head;
    while(cur->_next != nullptr) {
        pre = cur;
        cur = cur->_next;
    }
    delete cur;
    pre->_next = nullptr;
}

void LinkedList::push_front(int val) {
    Node* newNode = new Node(val, head->_next);
    head->_next = newNode;
}

void LinkedList::pop_front() {
    Node* p = head->_next;
    if(p != nullptr) {
        head->_next = p->_next;
        delete p;
    }
}

void LinkedList::remove(int val) {
    Node* cur = head->_next;
    Node* pre = head;
    while(cur != nullptr) {
        if(cur->_data == val) {
            pre->_next = cur->_next;
            delete cur;
            return;
        }
        else {
            pre = cur;
            cur = cur->_next;
        }
    } 
}

void LinkedList::removeAll(int val) {
    Node* cur = head->_next;
    Node* pre = head;
    while(cur != nullptr) {
        if(cur->_data == val) {
            pre->_next = cur->_next;
            delete cur;
            cur = pre->_next;//注意需要重置cur
        }
        else {
            pre = cur;
            cur = cur->_next;
        }
    } 
}
    
bool LinkedList::find(int val) {
    Node* cur = head->_next;
    while(cur->_next != nullptr) {
        if(cur->_data == val) {
            return true;
        }
        else {
            cur = cur->_next;
        }
    } 
    return false;
}
    
void LinkedList::show() {
    Node* cur = head->_next;
    while(cur) { 
        cout << cur->_data << " ";
        cur = cur->_next;
    }
    cout << endl;
}

//main.cc
#include "LinkedList.h" 
#include <iostream>
#include <time.h>
#include <stdlib.h>
using std::cout;
using std::endl;
 
int main(void)
{
    LinkedList list;

    srand(time(nullptr));
    for(int i = 0; i < 10; ++i) {
        list.push_back(rand()%100);
    }
    list.show();

    list.pop_back();
    list.pop_front();
    list.show();

    list.push_front(100);
    cout << list.find(100) << endl;
    list.remove(100);
    cout << list.find(100) << endl;
    
    list.push_back(100);
    list.push_back(100);
    list.push_back(100);
    list.show();
    list.removeAll(100);
    list.show();
}

$./main 
73 69 66 82 7 66 21 6 88 77 
69 66 82 7 66 21 6 88 
1
0
69 66 82 7 66 21 6 88 100 100 100 
69 66 82 7 66 21 6 88

单向循环链表

特点：

  • 每一个节点除了数据域，还有一个next指针域指向下一个节点(存储了下一个节点的地址)
  • 末尾节点的指针域指向了头节点

单向循环链表的实现

#include <iostream>
using std::cout;
using std::endl;

class CircleList {
public:
    CircleList() {
        _head = new Node();
        _head->_next = _head;
        _tail = _head;
    }
    
    ~CircleList(){
        Node* p = _head->_next;
        while(p != _head) { //循环链表结束条件
            _head = p->_next;
            delete p;
            p = _head;
        }
        delete _head;   //最后记得释放头结点
    }

    void insertTail(int val) {
        Node* newNode = new Node(val, _head);
        _tail->_next = newNode;
        _tail = newNode;
    }

    void insertHead(int val) {
        Node* newNode = new Node(val, _head->_next);
        _head->_next = newNode;
        if(newNode->_next == _head) {   //如果只有一个结点的情况
            _tail = newNode;
        }
    }

    void remove(int val) {
        Node* p = _head;
        Node* temp = nullptr;
        while (p->_next != _head) {
            if(p->_next->_data == val) {
                temp = p->_next;
                p->_next = p->_next->_next;
                delete temp;
                if(p->_next == _head) {
                    _tail = p;
                }
                return;
            }
            else{
                p = p->_next;
            }
        }
    }

    bool find(int val) const {
        Node* p = _head->_next;
        while(p != _head) {
            if(p->_data == val) {
                return true;
            }
        }
        return false;
    }

    void show() {
        Node* p = _head->_next;
        while(p != _head) {
            cout << p->_data << " ";
            p = p->_next;   //记得重置p
        }
        cout << endl;
    }
    
private:
    struct Node {
        int _data;
        Node* _next;
        Node(int data = 0, Node* next = nullptr) : _data(data), _next(next) {};
    };
    Node* _head;
    Node* _tail;
};


int main(void)
{
    CircleList clist;
    
    srand(time(nullptr));
    for(int i = 0; i < 10; ++i) {
        clist.insertTail(rand()%100);
    }
    clist.show();

    clist.insertHead(200);
    cout << clist.find(200) << endl;
    clist.remove(200);
    clist.show();

}

$./main 
98 13 13 33 99 6 2 35 15 18 
1
98 13 13 33 99 6 2 35 15 18

双向链表

特点：

  • 每一个节点除了数据域，还有next指针域指向下一个节点，pre指针域指向前一个节点
  • 头节点的pre是NULL，末尾节点的next是NULL

基础版

#include <iostream>
using std::cout;
using std::endl;

class DoubleLink{
public:
    DoubleLink() {
        _head = new Node();
    }

    ~DoubleLink() {
        Node* p = _head;
        while(p->_next) {
            _head = p->_next;
            delete p;
            p = _head;
        } 
        _head = nullptr;
    }

    void insertTail(int val) {
        Node* newNode = new Node(val);
        Node* p = _head;
        while(p->_next) {
            p = p->_next;
        }
        p->_next = newNode;
        newNode->_pre = p;
    }

    void insertHead(int val) {
        Node* newNode = new Node(val);
        newNode->_next = _head->_next;
        newNode->_pre = _head;
        
        if(_head->_next != nullptr) {
            _head->_next->_pre = newNode;
        }
        _head->_next = newNode; 
    }

    void remove(int val) {
        Node* p = _head;
        while(p) {
            if(p->_data == val) {
                p->_pre->_next = p->_next;
                if(p->_next) {  //注意加一个判断
                    p->_next->_pre = p->_pre;
                }
                delete p;
                return;
            }
            p = p->_next;
        }
    }
    
    bool find(int val) {
        Node* p = _head->_next; //有头结点的注意一下
        while(p) {
            if(p->_data == val) {
                return true;
            }
            p = p->_next;
        }
        return false;
    }

    void show() {
        Node* p = _head->_next;
        while(p) {
            cout << p->_data << " ";
            p = p->_next;
        }
        cout << endl;
    }

private:
    struct Node {
        int _data;
        Node* _pre;
        Node* _next;
        Node(int data = 0, Node* pre = nullptr, Node* next = nullptr) : _data(data), _pre(pre), _next(next) {}
    };
    Node* _head;
};



int main(void)
{
    DoubleLink dlink;
    dlink.insertHead(100);
    dlink.insertHead(10);
    dlink.insertHead(20);
    dlink.insertTail(30);
    dlink.insertTail(40);
    dlink.show();

    dlink.remove(100);
    dlink.remove(20);
    dlink.remove(40);
    dlink.show();
    cout << dlink.find(10);
}

升级版

LeetCode707 链表设计

双向循环链表

特点：

  • 每一个节点除了数据域，还有next指针域指向下一个节点，pre指针域指向前一个节点
  • 头节点的pre指向末尾节点，末尾节点的next指向头节点
Copyright © 2024 张威