当前课程知识点：数据结构（Data Structures） > 2. List > 2.6 Insertion Operation on Linked list > Video
返回《数据结构（Data Structures）》慕课在线视频课程列表
返回《数据结构（Data Structures）》慕课在线视频列表
在这节课中
我将给大家讲解一下
链表上的插入操作
当我们要往栅栏的位置
插入一个元素的时候
比如在图中这个例子里面
我们要插入10
那么我们首先就要去构建一个新的结点
用来去存放这个10
然后我们要把这个结点
插入到fence结点的后面
因为链表的结点之间
是通过next指针联系在一起的
因此在链表中插入结点的过程
就是要去修改他们结点的next指针
我们可以让新结点 它的next指针
指向原来栅栏后面的结点
然后再让fence结点 它的next指针
指向新的结点
这样我们就实现了
把新结点插入到链表的过程
下面我们来看一下
这个插入过程的实现
insert函数将会实现
把数据元素item插入到栅栏位置的后面
首先我们要创建一个新的结点
这是通过new Node的语句来实现的
新创建的结点它的数据元素是item
它的next指针
将会指向fence的下一个结点
当我们创建好这个结点之后
我们要去修改fence结点它的next指针
我们让这个指针指向新创建的结点
同时我们会给列表的长度加1
程序写到这里似乎可以结束了
但是我们在实现一个类的函数的时候
应当要注意
当每一个函数执行完的时候
所有类的成员属性
应该处于一个正确的状态
我们可以看到这个插入的过程
对head以及fence不会构成影响
那么它会不会对这个tail构成影响呢
我们来看这样一个特殊的例子
如果在插入之前
这个栅栏是处于最末端的位置
这个时候fence和tail它是重叠的
在这种情况下
如果我们要在栅栏后面插入一个新的结点
那么链表的末尾元素就变成了这个新结点
所以在这种情况下
我们应当修改tail指针
让它指向新插入的结点
我们可以看到在整个插入过程中
没有循环语句
可以在常数时间内完成
因此这个算法的复杂度是Θ(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
