知识点
链表是一种通过指针串联在一起的线性结构,每一个节点是又两部分组成,一个是数据域一个是指针域(存放指向下一个节点的指针),最后一个节点的指针域指向null(空指针的意思)。
类型
单链表
双链表
每一个节点有两个指针域,一个指向下一个节点,一个指向上一个节点。
既可以向前查询也可以向后查询。
循环链表
循环链表,顾名思义,就是链表首尾相连。
循环链表可以用来解决约瑟夫环问题。
链表的存储方式
链表中的节点在内存中不是连续分布的 ,而是散乱分布在内存中的某地址上,分配机制取决于操作系统的内存管理。
定义
c/c++一般用结构体来定义一个链表节点。
struct node{
int val;//data
node *next;//指向下一个节点的指针
//自定义构造函数可以在初始化节点时直接赋值
node(int x):val(x),next(NULL){} //构造函数的极简写法
}
class ListNode{
constructor(val){
this.val =val
this.next =null
}
}
链表操作
删除节点
将C节点指针指向E,在C/C++中手动释放D的内存,JAVA、Python有自动内存回收机制。
时间复杂度:O(1)+查找
添加节点
将C节点指针指向F,F指向D
时间复杂度:O(1)+查找