链表

链表基本组成

链表(linked list)属于线性数据结构，其主要由数据本身和指向下一节点的指针构成。

在一般的链表中，头节点为第一个节点，在某些实现中，头节点本身不包含元素，尾节点的next指针指向'空’，其本身为null，nullptr或者None。

graph LR subgraph head A`[next] end head-->1 subgraph 1 B[1] B`[next] end 1-->2 subgraph 2 C[2] C`[next] end 2-->3 subgraph 3 D[3] D`[next] end 3-->4 subgraph 4 E[4] E`[next] end 4 -->None subgraph None F`[null] end

其基本组成单位是节点(node),与数组不同，每个节点在计算机的内存中都是随机存放的，所有要找到下一个节点所在的位置就需要存储下一节点位置的指针，因此通常情况下链表所占用的内存空间要大于数组。

class Node{
	public:
		int val;
		Node* next;
		Node(int value): val(value), next(nullptr) {} //构造函数 赋值
};

链表的基础操作

1. 链表初始化

链表初始化分为两步，先将节点赋值，再构建节点之间的关系，当链表正确初始化之后便可以从头节点开始遍历所有元素了。

Node* node1 = new Node(1);
Node* node2 = new Node(2);
Node* node3 = new Node(3);
Node* node4 = new Node(4);
//创建节点并赋值
node1->next = node2;
node2->next = node3;
node3->next = node4;
//连接节点

2. 插入

链表的插入本质上是在内存中开辟一个单位的Node空间，赋值后将插入位置的前一个节点Node(n)的next指针指向这块内存，将该节点next指针指向原链表之后的节点Node(n+1),相比数组更快，因此时间复杂度仅为$O(1)$.

Node* insert(Node* node, Node* head){
     //直接在尾节点处插入
	if(head == nullptr) return node;
	Node* curr = head;
	while(curr->next && curr){   //在尾节点插入复杂度为O(n)
		curr = curr->next;
		}
	curr->next = node;
	return head;
}

Node* insert2(Node* node, Node* p){
	//在p节点之后插入
    Node* tmp = p->next;
	p->next = node;
	node->next = tmp;
	return node;
}

3. 删除

删除与插入的逻辑基本相同，找到待删除节点，与其前驱，将前驱的next节点指向待删除结点的next节点，然后删去该节点。

void deletenode(Node* n){
	//删去n之后的首个节点
	Node* tmp;
	if(n == nullptr || n ->next == nullptr) return;
	tmp = n->next->next;
	delete(n->next);
	n->next = tmp;
}

4. 访问与查找节点

在链表中访问节点的速度较慢，每次必须从头节点开始遍历直到找到，其时间复杂度为$O(n)$, 而数组的访问为$O(1)$.

Node* access(Node* head, int index){
	Node* curr = head;
	for(int i = 0; i < index; i++){
		if(curr == nullptr) return curr;
		curr = curr->next;
	}
	return curr;
}
Node* find(Node* head, int val){
    //查找第一个值为val的节点
	Node* curr = head;
    while(curr != nullptr){
		if(curr->val == val) return curr;
        curr = curr->next;
    }
    return nullptr;
}

常见的链表

单向链表 ：即上述介绍的链表，只能单方向地从头节点遍历到尾节点，在进行插入删除等操作时，需要随时保存前驱节点。
双向链表 : 相比单向链表增加了prev指针用于保存上一个节点，在使用时更加灵活，但是也加大了内存开销。

graph LR subgraph head A`[next] end head-->1 subgraph 1 B[1] B`[next] end 1-->2 1-->head 2-->1 subgraph 2 C[2] C`[next] end 2-->3 3-->2 subgraph 3 D[3] D`[next] end 3-->4 4-->3 subgraph 4 E[4] E`[next] end 4 -->None None-->4 subgraph None F`[null] end
```
class ListNode{
public:
//双向链表
  int val;
  Node* next;
  Node* prev;
  Node(int value): val(value), next(nullptr), prev(nullptr) {} //构造函数 赋值
};
```
环形链表 : 即将单向链表的尾节点next指针指向头节点而不再指向`空`，在环型链表中任意节点都可以视作头节点。

graph LR subgraph 1 B[1] B`[next] end 1-->2 subgraph 2 C[2] C`[next] end 2-->3 subgraph 3 D[3] D`[next] end 3-->4 subgraph 4 E[4] E`[next] end 4 -->1

blog collcetions

链表基础总结

链表