算法_链表_基础知识&总结

链表的定义

c++中的定义方法：

struct LinkNode{
	int val; //节点上存储的元素
	LinkNode *next;  //指向下一个节点的指针
	LinkNode(int x): val(x),next(NULL){} //节点的构造函数
1
2
3
4

python中的定义方法：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
1
2
3
4

链表的操作

1. 删除节点
   
   在C++里最好是再手动释放这个D节点，释放这块内存。

   其他语言例如Java、Python，就有自己的内存回收机制，就不用自己手动释放了。

2. 添加节点
   
   可以看出链表的增添和删除都是O(1)操作，也不会影响到其他节点。

   但是要注意，要是删除第五个节点，需要从头节点查找到第四个节点通过next指针进行删除操作，查找的时间复杂度是O(n)。

性能分析

链表的特性和数组的特性对比：

数组：长度固定，查询快，增删慢
链表：长度不固定，查询慢，增删快