使用单指针实现双链表（C++语言）

本文主要是介绍使用单指针实现双链表（C++语言），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

本文是Clifford A. Shaffer所著《数据结构与算法分析》（C++版）习题4.4的解答。

链表是常见的数据结构，链表中的结点通常定义如下。

template <typename E> class Link {
public:E element;Link<E> *next;Link(const E& it, Link<E>* next) { }
};

结点是一个定义为Link的模板类，其元素element的类型E可以代入不同的具体类型，指针成员nex指向下一个结点。只有一个指针的结点只能用于单链表，在使用时需要保存一个头指针head，搜索链表的时候，每次都要从head开始，而且只能向后搜索，不能向前搜索。

双链表中的结点含有两个指针域，分别为prev和next，如下所示。

template <typename E> class Link {
public:E element;Link<E> *prev, *next;Link(const E& it, Link<E>* prev, Link<E>* next) { }
};

双链表在使用时可以保存一个头指针head，一个尾指针next。既可以从head出发向后搜索，也可以从tail出发向前搜索。如果再增加一个当前指针curr，那么在单链表中，只能从curr出发向后搜索，而在双链表中，可以从curr出发向后或者向前搜索。

基于结点类，可以设计链表类，下面的抽象数据类型给出了链表类所需要支持的基本操作。

template <typename E> class List { // List ADT
private:void operator =(const List&) {} List(const 

这篇关于使用单指针实现双链表（C++语言）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---