链表单向链表跳跃链表

单向链表  link list

t数组的局限：编译期就需要知道大小； 内存连续，插入困难

    // 链表节点类 包含一个信息 和指向下一个 节点的指针clas IntLLNode{public:IntLLNode(){// 默认构造函数   没有info信息nextPtr_ = 0;// 空指针}IntLLNode(int data, IntLLNode* in = 0){// 第二个构造函数info_    = data;nextPtr_ = in;}public:int info_;          // 包含一个信息          对用户很重要IntLLNode* nextPtr_;// 指向下一个 节点的指针  用于将节点连接起来组成链表}// 定义一个 节点指针IntLLNode* pt = new IntLLNode(10);//新建一个节点 其地址 赋给一个指向 IntLLNode 的指针 pt////   [pt]  ----> |  10 | 也就是 pt->info_   也就是 (*pt).info_//               |  \  | 也就是 pt->nextPtr_ 也就是 (*pt).nextPtr_ // 再定义一个节点pt->nextPtr  = new IntLLNode(30);//新建一个节点 其地址 赋给一个指向 IntLLNode 的指针 pt->nextPtr_////   [pt]  ----> |  10 |  //               |     |  -----> | 30 | 也就是 pt->nextPtr_->info_//                               | \  | 也就是 pt->nextPtr_->nextPtr_// 再定义一个节点pt->nextPtr_->nextPtr_  = new IntLLNode(50);//新建一个节点 其地址 赋给一个指向 IntLLNode 的指针 pt->nextPtr_->nextPtr_////   [pt]  ----> |  10 |  //               |     |  -----> | 30 |  //                               |    | ------> | 50 | 也就是  pt->nextPtr_->nextPtr_->info_//                                              |  \ | 也就是  pt->nextPtr_->nextPtr_->nextPtr_

使用 头结点和尾节点来存储链表结构

 //************************  intSLList.h  **************************// 单链表 实现类 #ifndef INT_LINKED_LIST#define INT_LINKED_LIST// 单个节点// 定义一个 节点指针// IntLLNode* pt = new IntLLNode(10);//新建一个节点 其地址 赋给一个指向 IntLLNode 的指针 pt////   [pt]  ----> |  10 | 也就是 pt->info_   也就是 (*pt).info_//               |  \  | 也就是 pt->nextPtr_ 也就是 (*pt).nextPtr_  class IntSLLNode {public:IntSLLNode() {// 默认构造函数   没有info信息next = 0;// 空指针}IntSLLNode(int data, IntSLLNode *ptr = 0) {// 第二个构造函数info = data; next = ptr;}public:    int info;         // 包含一个信息          对用户很重要IntSLLNode *next; // 指向下一个 节点的指针  用于将节点连接起来组成链表};// 链表 类  保存了一个 头节点 和 一个尾节点 class IntSLList {public:IntSLList() {// 默认构造函数  这里定义和实现 head = tail = 0;// 节点 和 一个尾节点 指针赋值为 空 }~IntSLList();// 默认析构函数  只有定义 实现在 cpp文件中 int isEmpty() {//为空链表是否 return head == 0;}void addToHead(int);   // 从头部添加 节点 void addToTail(int);   // 从尾部添加 节点 int  deleteFromHead(); // 从头部删除 节点 并返回该节点的信息 int  deleteFromTail(); // 从尾部删除 节点 并返回该节点的信息 void deleteNode(int);//删除 bool isInList(int) const;void printAll() const;//打印所有的节点的信息   private:IntSLLNode *head, *tail;// 保存了一个 头节点 和 一个尾节点};

#endif

实现类cpp intSLList.cpp

头部插入节点   head 和 tail  仅仅是保存了 一个(节点)存储的地址

   head ---> | 5 |  |   | ---> | 7 ||   | --->  |  4 | <-------- tail|    |新建一个节点                                 | 9 |  head ---> | 5 |  |   |            |   | ---> | 7 ||   | --->  |  4 | <-------- tail|    |   新节点指向 head 指向的地址   new IntSLLNode9, head);| 9 |  head ---> | 5 |  |   | ------->   |   | ---> | 7 ||   | --->  |  4 | <-------- tail原头结点指向新节点  head = new IntSLLNode(9,head);head --->  |   | | 9 |  |   | -------> | 5 |  |   | ---> | 7 ||   | --->  |  4 | <-------- tail

|   |

尾部插入一个节点

 head ---> | 5 |  |   | ---> | 7 ||   | --->  |  4 | <-------- tail|    |尾部新建一个节点     new IntSLLNode(9);                             head ---> | 5 |  |   | ---> | 7 ||   | --->  |  4 | <-------- tail|    |                 | 9 |   | \ |                                 tail指向的节点 指向这个新节点   tail->next = new IntSLLNode(9)head ---> | 5 |  |   | ---> | 7 ||   | --->  |  4 | <-------- tail|    | -------->   | 9 |   | \ | 尾节点tail 指向新的 尾节点   tail = tail->next;head ---> | 5 |  |   | ---> | 7 ||   | --->  |  4 | |    | -------->  | 9 |   <-------- tail| \ |                                 

双向向链表  link list  节点同时包含 指向前驱节点的指针 也包含 指向后继节点的指针

双向向链表

跳跃链表

跳跃链表

标准库中的链表 list #include

 //一些成员函数assign(iterator first, iterator last) 删除所有节点，在first到last插入元素assign(size_type n, el) 删除所有节点，向其中插入n个elback()  尾节点元素front() 第一个节点元素clear() 删除所有节点empty() 判断是否为空erase() 删除一个节点insert() 插入一个元素pop_back() 删除最后一个节点pop_front() 删除第一个节点push_back() 在表尾插入push_front() 在表头插入sort()       排序swap()      与另一个链表互换unique()   从有序链表中删除重复的元素

测试代码

#include <iostream>
#include <list>//链表 
#include <algorithm>// 算法 
#include <deque>//队列 
#include <functional>using namespace std;// 打印链表每一个元素 
template<class T>
void printList(const list<T>& lst, char *s) {cout << s << ":  ";for (typename list<T>::const_iterator i = lst.begin(); i != lst.end(); ++i)cout << *i << ' ';cout << endl;
}int main() {list<int> lst1;// 创建空链表                     printList(lst1,"lst1");     // lst1 is emptylist<int> lst2(3,7);            printList(lst2,"lst2");     // lst2 = (7 7 7)for (int j = 1; j <= 5; j++)// lst1 = (1 2 3 4 5)lst1.push_back(j);//尾后插入元素 list<int>::iterator i1 = lst1.begin(), i2 = i1, i3;i2++; i2++; i2++;list<int> lst3(++i1,i2);        printList(lst3,"lst3");     // lst3 = (2 3)list<int> lst4(lst1);printList(lst4,"lst4");     // lst4 = (1 2 3 4 5)i1 = lst4.begin();lst4.splice(++i1,lst2);         printList(lst2,"lst2");     // lst2 is emptyprintList(lst4,"lst4");     // lst4 = (1 7 7 7 2 3 4 5)lst2 = lst1;printList(lst2,"lst2");     // lst2 = (1 2 3 4 5)i2 = lst2.begin();lst4.splice(i1,lst2,++i2);      printList(lst2,"lst2");     // lst2 = (1 3 4 5)printList(lst4,"lst4");     // lst4 = (1 7 7 7 2 2 3 4 5)i2 = lst2.begin();i3 = i2;lst4.splice(i1,lst2,i2,++i3);printList(lst2,"lst2");     // lst2 = (3 4 5)printList(lst4,"lst4");     // lst4 = (1 7 7 7 2 1 2 3 4 5)lst4.remove(1);         printList(lst4,"lst4");     // lst4 = (7 7 7 2 2 3 4 5)lst4.sort();                            printList(lst4,"lst4");     // lst4 = (2 2 3 4 5 7 7 7)lst4.unique();                          printList(lst4,"lst4");     // lst4 = (2 3 4 5 7)lst1.merge(lst2);                        printList(lst1,"lst1");     // lst1 = (1 2 3 3 4 4 5 5),printList(lst2,"lst2");     // lst2 is emptylst3.reverse();                         printList(lst3,"lst3");     // lst3 = (3 2)     lst4.reverse();printList(lst4,"lst4");     // lst4 = (7 5 4 3 2)lst3.merge(lst4,greater<int>());  printList(lst3,"lst3");     // lst3 = (7 5 4 3 3 2 2)printList(lst4,"lst4");     // lst4 is emptylst3.remove_if(bind2nd(not_equal_to<int>(),3));printList(lst3,"lst3");     // lst3 = (3 3)lst3.unique(not_equal_to<int>());printList(lst3,"lst3");     // lst3 = (3 3)return 0;
}