链表基础操作

链表基础知识

在数据结构的学习过程中，我们知道线性表【一种数据组织、在内存中存储的形式】是线性结构的，其中线性表包括顺序表和链表。数组就是顺序表，其各个元素在内存中是连续存储的。
链表则是由数据域和指针域组成的结构体构成的，数据域是一个节点的数据，指针域存储下一个节点的地址，下一个节点依靠上一个节点的指针域寻址。给出整个链表的头节点地址（指针）head后，就能依次访问链表的每个节点。
链表定义：

链表是一种递归的数据结构，它或者为空（null），或者是指向一个结点（node）的引用，该节点还有一个元素和一个指向另一条链表的引用。

根据链表间节点的指向，链表可以分为以下三种：

• 单向链表：指针域中只有指向下一个节点的地址；只能单向遍历链表；
  
• 双向链表：指针域中有两个指针，一个指向前一个节点，一个指向下一个节点；可以双向遍历链表；
  
• 循环链表：链表形成环，最后一个节点的指针域不赋值为null，而是指向头节点head；
  

定义一个链表节点，是单向的链表：

	//定义一个结构体ListNode表示链表节点struct ListNode {int val;   //数据域，这里用的int，根据实际情况选择type，比如char、float等ListNode *next; //指针域，存下一个节点的地址，所以是指针类型，并且下一个节点也是该结构体，所以是ListNode*//自定义构造函数，给数据域和指针域赋值ListNode() : val(0), next(nullptr) {}ListNode(int x) : val(x), next(nullptr) {}ListNode(int x, ListNode *next) : val(x), next(next) {}};

链表中头节点直接用head指针访问，其他节点用currentNode->next的指针访问，可见链表的头节点是特殊的。在插入、删除操作中，针对头节点都需要做特殊的处理，会较麻烦，因此在头节点前增加一个虚拟头节点【也叫附加头节点、哨兵节点等】dummy_head，虚拟头节点的指针域存head，即dummy_head->next = head；数据域无效，因为后续不会用到。给定dummy_head后，其他节点都用当前节点的next指针访问，即currentNode->next：

接下来介绍对链表进行的一些操作【穿针引线法】：

插入节点

在链表中的一个位置插入节点，需要先断开插入位置前后两个节点的链接，再和这两个节点建立新的链接：先cur->next = pre->next；再pre->next = cur； 如果先pre->next = cur，就会丢失sur这个节点的地址。

上面是普通的情况，那么针对头节点，尾节点的特殊情况呢？ 末尾节点其实也没有什么特殊的，只是suc是NULL，也就是pre->next为NULL，按照上述的两步操作也是ok的。问题是在头节点前插入：

• 如果是普通链表，头节点前什么都没有，pre是NULL的。只进行①：cur->next = head，head = cur【头节点是新插入的节点】；
• 如果前面有虚拟头节点，那么pre就是dummy_head，头节点和其他节点是一样的操作；

删除节点

从链表中删除节点，可以是删除指定位置的，比如删除第三个节点；也可以是根据节点值删除的，比如删除值等于target的节点。删除节点时，将被删除节点的前面节点和后面节点连接起来的同时，断开被删除节点和其前面一个、后面一个节点的连接，并且要释放掉被删除节点的空间：pre->next = cur->next；delete cur。

针对头节点和尾节点的特殊情况呢？ 将尾节点看作是下一个节点是null的节点，处理和其他节点一样。问题同样是头节点，删除头节点的话：

• 普通链表，直接tmp = head->next，delete head，head = tmp；
• 添加了虚拟头节点的链表，删除头节点，其pre = dummy_head，cur = head；直接按照正常节点删除即可。
  从删除头节点和在头节点前插入节点的分析就可以知道，添加了虚拟头节点dummy_head后，对头节点的操作不需要单独讨论，所有节点操作一致。

查找节点

比如按位置查找某个节点，返回其节点值；比如按值查找链表中是否存在值等于target的节点。因为链表是通过节点的指针域而将各个节点连接起来的，它不能像数组一样直接按下标查找【数组各元素在内存空间是连续存储的，通过下标就能够定位到内存空间】。要查找链表中某个节点，需要遍历链表，需要O(n)的时间复杂度。

707. 设计链表

题目链接：707.设计链表
题目内容：

理解题意：实际上就是实现一个链表类，可以单向也可以双向，其中要涉及到插入节点：在头部插入、在尾部插入、根据下标index在指定位置插入；删除节点；根据下标index获取节点值。

实现：单向链表：

以下代码实现的是有虚拟头节点的单向链表，并且在类中定义一个_size变量存储链表中节点数量，以便根据下标index删除、添加节点时，判断下标是否合理。 另外在节点末尾处添加节点，可认为是index = _size时，在index处插入节点：

class MyLinkedList {
private://定义类的私有变量int _size;   //链表中节点数量，不包括虚拟头节点//定义链表节点结构体struct ListNode {int val;   //数据域ListNode *next;  //指针域//构造函数ListNode() : val(0), next(nullptr) {}ListNode(int x) : val(x), next(nullptr) {}ListNode(int x, ListNode *next) : val(x), next(next) {}};//链表附加头节点，整个链表的开始ListNode* _dummyhead;
public:    //自定义类的构造函数MyLinkedList() {_dummyhead = new ListNode(0); //新建虚拟头节点_size = 0; //初始化链表中有效节点数量为0}//根据下标返回节点valueint get(int index) {//下标无效if(index >= _size)return -1;ListNode* currNode = _dummyhead; //从虚拟头节点开始访问//遍历到下标为index的节点for(int i = 0; i <= index; i++){currNode = currNode->next;}        return currNode->val;  //返回value}//在头部添加节点void addAtHead(int val) {ListNode * newNode = new ListNode(val); //先构造一个新节点newNode->next = _dummyhead->next; //直接在虚拟头节点后插入_dummyhead->next = newNode;_size++;   //插入节点后，链表节点数量+1}//在尾部添加节点 //实际上就是在index为_size的地方添加节点void addAtTail(int val) {addAtIndex(_size,val);}//在指定下标index位置处插入节点void addAtIndex(int index, int val) {if(index > _size) return ;  //下标不合理ListNode* newNode = new ListNode(val); //构造一个新节点ListNode* prevNode = _dummyhead;//找到需要插入的地方while(index)  {prevNode = prevNode->next;index--;}   //插入节点   newNode->next = prevNode->next;prevNode->next = newNode;_size++;  //节点数量++}//删除指定位置的节点void deleteAtIndex(int index) {if(index >= _size) return;  //下标不合理ListNode* prevNode = _dummyhead;//找到要删除的节点的前一个节点while(index){prevNode = prevNode->next;index--;}//tmp为要删除的节点ListNode* tmp = prevNode->next;//要删除节点前后两个节点建立新连接prevNode->next = tmp->next;//删除tmp节点，释放空间delete tmp;_size--; //链表中节点数量-1；}
};

实现：双向链表

双向链表就是每个节点有两个指针，一个指向前驱节点（preNode），一个指向后驱节点（succNode），插入、删除节点时，需要对两个指针的指向都处理：

• 插入一个节点时，preNode->next = newNode； newNode->next = succNode； succNode->prior = newNode； newNode->prior = preNode；
• 删除一个节点时：preNode->next = succNode；succNode->prior = preNode；
  这里需要注意的是，succNode实际上是currNode->next，如果是删除最后一个节点或者在最后一个节点后追加一个节点，succNode=NULL，为了和其他节点统一操作，同样在末尾增加一个虚拟尾节点。
  双向链表可以双向遍历，在index位置插入、删除、查询节点值时，可以先判断index是在链表前半段还是后半段，确定是从前往后遍历更快，还是从后往前遍历更快。 代码如下（C++）：

class MyLinkedList {
private:int _size;   //链表中有效节点数量，不包括虚拟头节点、虚拟尾节点struct ListNode {  //定义链表节点结构体int val;ListNode *next, *prior;  //双向链表需要有两个指针ListNode() : val(0), next(nullptr), prior(nullptr) {}ListNode(int x) : val(x), next(nullptr), prior(nullptr) {}ListNode(int x, ListNode *next, ListNode *prior) : val(x), next(next), prior(prior) {}};ListNode *_dummyhead, *_dummytail; //虚拟头节点和虚拟尾节点
public:    MyLinkedList() {_dummyhead = new ListNode(0); //虚拟头节点_dummytail = new ListNode(0); //虚拟尾节点//建立虚拟头节点和虚拟尾节点之间的连接_dummyhead->next = _dummytail;  _dummytail->prior = _dummyhead;_size = 0; //链表中有效节点数量}int get(int index) {//下标无效if(index >= _size)return -1;ListNode *currNode;//判断index在前半段if(index < _size/2){currNode = _dummyhead;//从前往后遍历更快for(int i = 0; i <= index; i++){currNode = currNode->next;} }else{ //index在后半段currNode = _dummytail;//从后往前遍历更快for(int i = _size-1; i >= index ;i--){currNode = currNode->prior;}}return currNode->val;}//在头部添加节点，即在虚拟头节点后插入void addAtHead(int val) {ListNode *newNode = new ListNode(val);//建立四条新的连接_dummyhead->next->prior = newNode;newNode->next = _dummyhead->next;_dummyhead->next = newNode;newNode->prior = _dummyhead;_size++;}//在尾部插入节点，等于在index = _size的位置插入节点void addAtTail(int val) {addAtIndex(_size,val);}//在指定index处插入void addAtIndex(int index, int val) {if(index > _size) return ;ListNode* newNode = new ListNode(val);ListNode *prevNode = _dummyhead, *succNode = _dummytail;if(index < _size/2){ //从前往后更快定位到index前的节点for(int i = 0; i < index; i++){prevNode = prevNode->next;}succNode = prevNode->next;}else{ //从后往前更快定位到index前的节点for(int i = _size - 1; i >= index; i--){succNode = succNode->prior;}prevNode = succNode->prior;}//插入一个节点后，新增四条连接succNode->prior = newNode;     newNode->next = succNode;prevNode->next = newNode;newNode->prior = prevNode;_size++;}//删除index处的节点void deleteAtIndex(int index) {if(index >= _size) return;ListNode *prevNode = _dummyhead, *succNode = _dummytail;//根据index和_size的关系，决定从前往后遍历还是从后往前遍历if(index < _size/2){for(int i = 0; i < index; i++){prevNode = prevNode->next;}succNode = prevNode->next->next;}else{for(int i = _size - 1; i > index; i--){succNode = succNode->prior;}prevNode = succNode->prior->prior;}ListNode* tmp = prevNode->next;//preNode和succNode之间建立双向连接prevNode->next = succNode;        succNode->prior = prevNode;delete tmp;_size--;}
};