首页 > 其他分享 >链表与list

链表与list

时间：2022-12-13 23:37:13浏览次数：79  
标签：Node head cur val list next 链表 _-

1. 链表实现

特点: 每一个节点都是在堆内存上独立 new 出来的，节点内存不连续。即逻辑地址连续，而物理地址不连续。

优点：

  • 内存利用率高，不需要大块连续内存
  • 插入和删除节点不需要移动其它节点，时间复杂度 O(1)
  • 不需要专门进行扩容操作

缺点：

  • 内存占用量大，每一个节点多出存放地址的空间
  • 节点内存不连续，无法进行内存的随机访问
  • 链表的搜索效率不高，只能从头节点开始逐结点遍历

常见的链表形式包括：单链表、双向链表、环状链表

1.1 单链表

单链表的定义：每一个节点只能找到下一个节点，而无法找到上一个节点，如下图所示：

特点：

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

如下代码为单链表的实现：

// 链表节点定义
struct Node {
    Node(int val = 0)
        : data_(val)
        , next_(nullptr) { }
    int   data_;
    Node* next_;
};

class SList {
public:
    SList();
    ~SList();

public:
    // 尾插法
    void push_back(int val);
    // 头插法
    void push_front(int val);
    // 删除第一个值为 val 节点
    void remove(int val);
    // 删除所有值为 val 的节点
    void removeAll(int val);
    // 搜索是否存在值为 val 的元素
    bool find(int val);
    // 打印
    void print() const;

private:
    Node* head_; // 链表头节点
};

SList::SList()
    : head_(new Node) {
}

SList::~SList() {
    while (head_->next_ != nullptr) {
        Node* node   = head_->next_;
        head_->next_ = node->next_;
        delete node;
    }
    delete head_;
    head_ = nullptr;
}

void SList::push_back(int val) {
    Node* cur = head_;
    while (cur->next_ != nullptr) {
        cur = cur->next_;
    }
    cur->next_ = new Node(val);
}

void SList::push_front(int val) {
    Node* node   = new Node(val);
    node->next_  = head_->next_;
    head_->next_ = node;
}

void SList::remove(int val) {
    Node* cur = head_;
    while (cur->next_ != nullptr) {
        if (cur->next_->data_ == val) {
            Node* node = cur->next_;
            cur->next_ = node->next_;
            delete node;
            break;
        }
        cur = cur->next_;
    }
}

void SList::removeAll(int val) {
    Node* cur = head_;
    while (cur && cur->next_ != nullptr) {
        if (cur->next_->data_ == val) {
            Node* node = cur->next_;
            cur->next_ = node->next_;
            delete node;
        } else {
            cur = cur->next_;
        }
    }
}

bool SList::find(int val) {
    Node* cur = head_->next_;
    while (cur) {
        if (cur->data_ == val) {
            return true;
        }
        cur = cur->next_;
    }
    return false;
}

void SList::print() const {
    Node* cur = head_->next_;
    while (cur != nullptr) {
        cout << cur->data_ << "->";
        cur = cur->next_;
    }
    cout << endl;
}

1.2 单向循环链表

特点：

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

其代码的实现如下：

class CircleLink {
public:
    CircleLink();
    ~CircleLink();
  
public:
    // 尾插法
    void push_back(int val);
    // 头插法
    void push_front(int val);
    // 删除第一个值为 val 的节点
    void remove(int val);
    // 查询是否存在值为 val 的节点
    bool find(int val);
    // 打印
    void print() const;
  
private:
    struct Node {
        Node(int data = 0)
            : data_(data)
            , next_(nullptr) { }
        int   data_;
        Node* next_;
    };
  
    Node* head_;
    Node* tail_;
};

CircleLink::CircleLink()
    : head_(new Node()) {
    tail_->next_ = head_;
    head_->next_ = head_;
}
  
CircleLink::~CircleLink() {
    Node* cur = head_->next_;
    while (cur != head_) {
        head_->next_ = cur->next_;
        delete cur;
        cur = head_->next_;
    }
    delete head_;
}
  
void CircleLink::push_back(int val) {
    Node* node   = new Node(val);
    node->next_  = tail_->next_;
    tail_->next_ = node;
    tail_        = node;
    if (head_->next_ == head_) {
        head_->next_ = node;
    }
}
  
void CircleLink::push_front(int val) {
    Node* node   = new Node(val);
    node->next_  = head_->next_;
    head_->next_ = node;
    if (node->next_ == head_) {
        tail_ = node;
    }
}
  
void CircleLink::remove(int val) {
    if (head_->next_ == head_) return;
    Node* cur = head_;
    while (cur->next_ != tail_) {
        if (cur->next_->data_ == val) {
            Node* nxt  = cur->next_;
            cur->next_ = nxt->next_;
            delete nxt;
            return;
        }
        cur = cur->next_;
    }
    if (tail_->data_ == val) {
        cur->next_ = tail_->next_;
        delete tail_;
        tail_ = cur;
    }
}
  
bool CircleLink::find(int val) {
    Node* cur = head_->next_;
    while (cur != head_) {
        if (cur->data_ == val)
            return true;
        cur = cur->next_;
    }
    return false;
}
  
void CircleLink::print() const {
    Node* cur = head_->next_;
    while (cur != head_) {
        cout << cur->data_ << "->";
        cur = cur->next_;
    }
    cout << endl;
}

1.3 双向链表

特点：

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

其代码实现如下：

class DoubleLink {
public:
    DoubleLink();
    ~DoubleLink();
  
    // 头插法
    void push_front(int val);
    // 尾插法
    void push_back(int val);
    // 删除
    void remove(int val);
    // 查找
    bool find(int val);
    // 打印
    void print() const;
  
private:
    // 节点类型
    struct Node {
        Node(int data = 0)
            : data_(data)
            , next_(nullptr)
            , prev_(nullptr) { }
        int   data_;
        Node* next_;
        Node* prev_;
    };
  
    Node* head_;
};

DoubleLink::DoubleLink()
    : head_(new Node()) {
}

DoubleLink::~DoubleLink() {
    Node* cur = head_;
    while (cur) {
        head_ = head_->next_;
        delete cur;
        cur = head_;
    }
}

void DoubleLink::push_back(int val) {
    Node* cur = head_;
    while (cur->next_ != nullptr) {
        cur = cur->next_;
    }
    Node* node  = new Node(val);
    cur->next_  = node;
    node->prev_ = cur;
    node->next_ = nullptr;
}
  
void DoubleLink::push_front(int val) {
    Node* node   = new Node(val);
    Node* nxt    = head_->next_;
    node->next_  = nxt;
    node->prev_  = head_;
    nxt->prev_   = node;
    head_->next_ = node;
}
  
void DoubleLink::remove(int val) {
    Node* cur = head_->next_;
    while (cur) {
        if (cur->data_ == val) {
            cur->prev_->next_ = cur->next_;
            if (cur->next_) {
                cur->next_->prev_ = cur->prev_;
            }
            delete cur;
            break;
        }
        cur = cur->next_;
    }
}
  
bool DoubleLink::find(int val) {
    Node* cur = head_->next_;
    while (cur) {
        if (cur->data_ == val) {
            return true;
        }
        cur = cur->next_;
    }
    return false;
}

void DoubleLink::print() const {
    Node* cur = head_->next_;
    while (cur) {
        cout << cur->data_ << "->";
        cur = cur->next_;
    }
    cout << endl;
}

1.4 双向循环链表

特点：

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

其代码实现如下：

class DoubleCircleLink {
public:
    DoubleCircleLink();
    ~DoubleCircleLink();
  
    // 头插法
    void push_front(int val);
    // 尾插法
    void push_back(int val);
    // 删除
    void remove(int val);
    // 查找
    bool find(int val);
    // 打印
    void print() const;

private:
    // 节点类型
    struct Node {
        Node(int data = 0)
            : data_(data)
            , next_(nullptr)
            , prev_(nullptr) { }
        int   data_;
        Node* next_;
        Node* prev_;
    };

    Node* head_;
};

DoubleCircleLink::DoubleCircleLink()
    : head_(new Node()) {
    head_->next_ = head_;
    head_->prev_ = head_;
}

DoubleCircleLink::~DoubleCircleLink() {
    Node* cur = head_->next_;
    while (cur != head_) {
        head_->next_      = cur->next_;
        cur->next_->prev_ = head_;
        delete cur;
        cur = head_->next_;
    }
    delete head_;
    head_ = nullptr;
}

void DoubleCircleLink::push_back(int val) {
    Node* node          = new Node(val);
    head_->prev_->next_ = node;
    node->next_         = head_;
    node->prev_         = head_->prev_;
    head_->prev_        = node;
}
  
void DoubleCircleLink::push_front(int val) {
    Node* node   = new Node(val);
    Node* nxt    = head_->next_;
    node->next_  = nxt;
    node->prev_  = head_;
    nxt->prev_   = node;
    head_->next_ = node;
}

void DoubleCircleLink::remove(int val) {
    Node* cur = head_->next_;
    while (cur != head_) {
        if (cur->data_ == val) {
            cur->prev_->next_ = cur->next_;
            cur->next_->prev_ = cur->prev_;
            delete cur;
            break;
        }
        cur = cur->next_;
    }
}
  
bool DoubleCircleLink::find(int val) {
    Node* cur = head_->next_;
    while (cur != head_) {
        if (cur->data_ == val) {
            return true;
        }
        cur = cur->next_;
    }
    return false;
}

void DoubleCircleLink::print() const {
    Node* cur = head_->next_;
    while (cur != head_) {
        cout << cur->data_ << "->";
        cur = cur->next_;
    }
    cout << endl;
}

2. 常见的算法问题

2.1 单链表逆序

如果采用暴力的方法，可以定义一个动态数组，然后遍历单链表，将单链表中的每个元素记录下来，然后使用双指针对数组进行逆序操作，完成之后又将数组变回单链表。如果采用这种方法，那么将会消耗掉很多的额外空间，造成资源的浪费。

更好的方法是进行原地逆序，即不采用额外的存储空间。其过程是对于头节点之后的所有元素，采用头插法依次插入到链表中即可，如下图所示：

练习题目: 206. 反转链表 - 力扣（LeetCode）

2.2 合并两个有序链表

由于两个链表是有序的，因此我们可以采用双指针的思想，对于要合并的链表，定义两个指针，一个指向当前节点，另一个指向当前节点的前驱节点，而对于另一个链表，则只需一个指针遍历即可，如下图所示：

其过程如下：

  1. 如果 point3 的数值小于 point1 的数值，执行 2，否则执行 8;
  2. point2 的 next 指向 point3;
  3. head2 的 next 指向 point3 的 next;
  4. point3 的 next 指向 point1;
  5. point2 移动到下一个元素;
  6. point3 指向 head2 的下一个元素;
  7. 重复步骤 1;
  8. point1 和 point2 均移动到下一个元素;

练习题目: 21. 合并两个有序链表 - 力扣（LeetCode）

2.3 访问倒数第k个元素

如果采用最暴力的方法，先遍历一次单链表，得到单链表的长度，然后再从头节点开始遍历，直到找到倒数第 k 个元素，那么其需要遍历两次单链表。

更好的一种方法是，使用双指针的思想，定义两个指针，一个快指针，一个慢指针。先让快指针找到正数第 k 个元素，然后慢指针从头开始走，如下图所示：

然后快、慢指针一块走，当快指针指向 NULL 的时候，慢指针所指的元素即为倒数第 k 个元素，如下图所示：

练习题目：19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

2.4 判断链表是否有环

判断一个单链表是否有环，我们依然可以采用双指针的思想，来分别定义一个快指针、一个慢指针，每一次，快指针走 2 步，而慢指针走 1 步。这就如同我们学过的 "追及相遇问题"，即两个人在操场上跑步，一个人跑的快，一个人跑的慢，从同一起点开始跑，两个人一定会在某一点处相遇。

如果要找到环的入口节点，那么该如何做？

我们先定义几个变量，从头节点到环入口的距离我们定义为变量 \(x\), 从环入口节点到相遇节点的距离定义为变量 \(y\)，从相遇节点到链表末节点的距离定义为变量 \(z\)，如图所示：

图中红色节点即为快、慢指针的相遇节点。由于快、慢指针相遇时，快指针所走的距离 \(s_1\) 为慢指针所走距离 \(s_2\) 的 2 倍，即存在 \(s_1=2*s_2\)，且由图可知：\(s_1=x+y+z+y\)，而 \(s_2=x+y\)，那么有如下推导过程：

\[s_1=s_2 \]

\[x+y+z+y=2x+2y \]

\[z=x \]

由于此时快慢指针均指向相遇节点，即图中的红色节点。那么让慢指针指向链表的头节点，慢指针和快指针同时向后走，一次走一步，两个指针相遇时，即为环入口节点。

练习题目: 剑指 Offer II 022. 链表中环的入口节点 - 力扣（LeetCode）

2.5 约瑟夫环

约瑟夫环是一个数学的应用问题: 已知 n 个人（以编号 1，2，3...n 分别表示）围坐在一张圆桌周围，从编号为 k 的人开始报数，数到 m 的那个人出列，它的下一个人又从 1 开始报数，数到 m 的那个人又出列，如此规律重复下去，直到圆桌周围的人全部出列，输出人的出列顺序。

约瑟夫环的典型应用就是单向循环链表。

3. STL 实现

3.1 list

STL 的 list 实现了双向循环链表数据结构，其本身和 list 的节点是不同的结构，其节点（node）结构如下：

template<class T>
struct __list_node {
    typedef void* void_pointer;
    void_pointer prev;
    void_pointer next;
    T data;
};

显然，这是一个双向链表，且是环状双向链表，如下图所示：

list 不能像 vector 一样使用普通指针作为迭代器，由于其是双向链表，所以迭代器必须具备前移、后移的能力，所以 list 提供的是 Bidirectional Iterators。而且，插入操作和接合操作都不会造成原有的 list 迭代器失效。甚至 list 的元素删除操作，也只有 “指向被删除元素” 的那个迭代器失效，其他迭代器不受任何影响。

3.2 slist

slist 是 SGI STL 所提供的单向链表，并不在标准规格之内。

其与 list 的主要区别在于：slist的迭代器属于单向的 Forward Iterator，而后者的迭代器属于双向的 Bidirectional Iterator。共同的特点是：插入、移除、接合等操作并不会造成原有的迭代器失效。

如图为 slist 的节点和迭代器的设计架构：

注意：比较两个迭代器是否等同时，由于 __slist_iterator 并未对 operator== 实施重载，所以会调用 __slist_iterator_base::operator==。根据其中定义可以发现两个 slist 迭代器是否相等取决于 __slist_node_base* node 是否相等。

而 operator*() 的定义则是通过将 node 强转为派生类来实现的：

template<class T, class Ref, class Ptr>
struct __slist_iterator : public __slist_iterator_base {
    typedef __slist_node<T> list_node;
    typedef Ref reference;
    reference operator*() const { return ((list_node*)node)->data; }
};

在 slist 的源码中，end() 的定义有所不同：

template<class T, class Alloc=alloc>
class slist {
    iterator end() { return iterator(0); }
};

如下图所示，其定义为 0：

标签：Node,head,cur,val,list,next,链表,_-
From： https://www.cnblogs.com/tuilk/p/16980967.html

相关文章

  • golang的net包net.Dial和net.Listen
    在Go中，网络编程主要通过net包实现。支持包括TCP/IP、UDP、域名解析和Unix域socket等连接，此外，还通过net/http，net/rpc等提供了HTTP，RPC等主流应用层的连接协议。TCP服......
  • Java类和对象2-API,String,ArrayList
    Java类和对象2-API,String,ArrayList如何使用帮助文档(API)先看这个类在哪个包里.看这个类的描述信息,知道这个类是干啥的.看构造方法.最后看成员方法,就是返回值,......
  • 线性表（链表，顺序表）讲解_legend
    线性表(linearList)（1）线性表的定义：节点（node）之间具有一对一的前驱后继关系（2）线性表的存储结构：（2.1）顺序表（sequenceList）:（2.2）链式表（linkList）:（3）顺序表的常见操作：（初始化+增删改......
  • 单链表的扩展操作21----legend050709
    单链表的操作之补充： (1).单链表的反转： (2).单链表的排序（插入排序，选择排序，冒泡排序等）： (3).单链表取得最小值的节点，及其前驱： (4).单链表获取最小的k个节点：（4-1）单链表......
  • bug？VS2010中CImageList::DrawIndirect总是返回失败
    //VS2010#if_MSC_VER>=1600pImageList->Draw(pDC,nImage,point,ILD_NORMAL);#elseSIZEsize;size.cx=rect.Width()<sizeImage.cx?rect......
  • A custom list view control with custom scrollbar control, using WTL
    Acustomlistviewcontrolwithcustomscrollbarcontrol,usingWTL Downloaddemoproject-197KbDownloadsource-200KbIntroductionThis......
  • TitleTips Support for Edit, ListBox and ComboBox Controls
    TitleTipsSupportforEdit,ListBoxandComboBoxControls Download1.10demoprojectsincludingDLLproject-230.36KBDownloadDLLbinariesfor......
  • Sort List Control
    SortListControl Downloadsourcefiles-1.58KbDownloaddemoproject-35.8KbIntroductionFirstthing,Iwouldliketoapologizeforanygr......
  • AttributeError: 'list' object has no attribute 'click'
    报错：AttributeError:'list'objecthasnoattribute'click'  说没有点击属性，我想着我这个元素就是需要点击怎么没有点击属性勒。我直接复制之前的代码，代码多了个s......
  • Unity UGUI无限列表（Infinite List）
    更新日期：2020年10月16日。Github源码：​​​[点我获取源码]​​索引​​InfiniteList​​​​使用​​​​创建InfiniteListScrollRect​​​​InfiniteListScrollRect参数......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99