当前课程知识点：数据结构（Data Structures） > 2. List > 2.7 Remove Operation on Linked list > Video
返回《数据结构（Data Structures）》慕课在线视频课程列表
返回《数据结构（Data Structures）》慕课在线视频列表
大家好
在接下来这节课中我将给大家讲解一下
链表上的删除操作
我们通过一个例子来去说明
删除操作的原理
在这个例子里面
我们要删除栅栏后面的结点
它包含的元素是10
我们只需要通过修改next指针
就可以实现这样的一个删除过程
具体来说我们可以让fence
它所指向的结点23的
next指针指向我们要删除的结点
它的后面那个结点 12
从而可以让这个连线绕过结点10
这样我们这个链表它的结点数目
就会减少1个
最后我们再把这个结点10进行销毁
就可以完成删除的过程
下面我们来看一下删除的具体实现
这里的remove函数
实现的是删除栅栏之后的结点
并且把这个结点中的数据元素的值
记录在引用参数it中
首先我们要检查一下
栅栏后面是否存在我们要删除的元素
如果fence它的next指针是空的
那么也就意味着
这个栅栏是处于最后的位置
它后面已经不存在结点了
所以这个删除要失败
返回false
而在一般的情况下
我们要删除的结点就是fence的next指针
所指向的那个结点
我们把这个结点的数据元素
记录在返回参数it中
然后我们用一个临时指针Itemp
指向这个要删除的结点
这样做
是为了方便我们后面的结点删除操作
然后我们去修改fence的next指针
让这个指针指向Itemp的下一个结点
从而可以使得我们这个链表的连接
绕过我们需要删除的结点
最后我们去释放删除的结点
同时我们将链表的长度减少一个
最后成功返回
程序写到这里是否可以结束了呢
我们仍然需要去注意所有的类成员属性
是否处于一个正确的状态
我们可以看到这个删除操作
不会对head以及fence造成任何的影响
但是对tail会不会又有影响呢
我们来看一下这样一个特殊的例子
如果我们删除的结点
是链表的最后一个结点
也就是Itemp和tail重叠的情况
在这种情况下如果我们去做删除操作
那么链表的末尾的元素将会发生改变
tail指针必须要相应的改变
我们需要让它去指向fence结点
综观我们整个删除操作过程
我们可以看到这个过程里面没有循环语句
可以在参数时间内完成
所以这个算法复杂度也是θ(1)
删除操作它的效率是比较高的
好的 这节课我们就讲到这里
下节课我们再见
-1. Introduction--1.1 Introduction of Data
-1.1 Introduction of Data Structure
--Introduction of Data Structure
-1.2 Data Structure and A
-1.2 Data Structure and Algorithm
--Video
-1.3 Asymptotic Analysis
-1.3 Asymptotic Analysis
--Video
-1.4 Simplifying Rules of
-1.4 Simplifying Rules of Asymptotic Analysis
--Video
-2.1 Introduction of List
-2.1 Introduction of List
--Video
-2.2 Array based List
-2.2 Array based List
--Video
-2.3 Insertion Operation on Array
-2.3 Insertion Operation on Array based List
--Video
-2.4 Remove Operation on Array based List
-2.4 Remove Operation on Array based List
--Video
-2.5 Linked list
-2.5 Linked list
--Video
-2.6 Insertion Operation on Linked list
-2.6 Insertion Operation on Linked list
--Video
-2.7 Remove Operation on Linked list
-2.7 Remove Operation on Linked list
--Video
-2.8 SetPos Operation on Linked list
-2.8 SetPos Operation on Linked list
--Video
-2.9 Stack
-2.9 Stack
--Video
-2.10 Application of Stack
--Video
-2.11 Queue
-2.11 Queue
--Video
-3.1 Definition of Binary Tree
-3.1 Definition of Binary Tree
--Video
-3.2 Implementation of Binary Tree
-3.2 Implementation of Binary Tree
--Video
-3.3Traversal
-3.3 Traversal
--Video
-3.4 Binary Search Tree
-3.4 Binary Search Tree
--Video
-3.5 Search on BST
-3.5 Search on BST
--Video
-3.6 Insertion on BST
-3.6 Insertion on BST
--Video
-3.7 Introduction of Heap
-3.7 Introduction of Heap
--Video
-3.8 Construction of Heap
-3.8 Construction of Heap
--Video
-3.9 Operations on Heap
--Video
-3.10 General Tree
--Video
-4.1 Definition of Searching
--Video
-4.2 Searching of Sorted Array
-4.2 Searching of Sorted Array
--Video
-4.3 Definition of Hash Table
--Video
-4.4 Collision in Hash Table
-4.4 Collision in Hash Table
--Video
-4.5 Extension of Linear Probing
--Video
-4.6 Insertion Operation of Hash Table
--Video
-4.7 Search Operation of Hash Table
-4.7 Search Operation of Hash Table
--Video
-5.1 Introduction of Index
--Video
-5.2 Linear Index
-5.2 Linear Index
--Video
-5.3 2-3 tree index
-5.3 2-3 tree index
--Video
-5.4 Implementation of 2-3 tree
-5.4 Implementation of 2-3 tree
--Video
-5.5 B-Tree
-5.5 B-Tree
--Video
-5.6 Insertion Operation on B+ Tree
--Video
-5.7 Deletion Operation on B+ Tree
--Video
-6.1 Definition of Graph
--Video
-6.2 Implementation of Graph
--Video
-6.3 Adjacency Matrix
--Video
-6.4 Adjacency List
--Video
-6.5 Graph Traversal - DFS
--Video
-6.6 Graph Traversal - BFS
--Video
-6.7 Topological Sort
--Video
-6.8 Shortest Path Problem
--Video
-6.9 Single Source Shortest Path
--Video
-6.10 Dijkstra Algorithm
--Video
-7.1 Sorting Problem
--Video
-7.2 Insertion Sort
--Video
-7.3 Selection Sort
--Video
-7.4 Bubble Sort
--Video
-7.5 Shell Sort
--Video
-7.6 Quick Sort
--Video
-7.7 Heap Sort
--Video
-7.8 Comparison
--Video
