链表基础操作
链表基础知识
在数据结构的学习过程中,我们知道线性表【一种数据组织、在内存中存储的形式】是线性结构的,其中线性表包括顺序表和链表。数组就是顺序表,其各个元素在内存中是连续存储的。
链表则是由数据域和指针域组成的结构体构成的,数据域是一个节点的数据,指针域存储下一个节点的地址,下一个节点依靠上一个节点的指针域寻址。给出整个链表的头节点地址(指针)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处插入节点:文章来源:https://www.toymoban.com/news/detail-664740.html
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
}
//根据下标返回节点value
int 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),插入、删除节点时,需要对两个指针的指向都处理:文章来源地址https://www.toymoban.com/news/detail-664740.html
- 插入一个节点时,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--;
}
};
到了这里,关于【leetcode 力扣刷题】链表基础知识 基础操作的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!