当前课程知识点：数据结构（Data Structures） > 2. List > 2.8 SetPos Operation on Linked list > Video
返回《数据结构（Data Structures）》慕课在线视频课程列表
返回《数据结构（Data Structures）》慕课在线视频列表
下面我们来学习一下
在链表中的SetPos操作它的实现
所谓SetPos操作
它的主要作用是用来去
设置栅栏的位置
这里的参数pos指定了我们要设定的位置
在链表中栅栏的位置的值最小是0
对应的是链表最左边的位置
而栅栏位置最大值
它是等于链表的长度length
对应的是在链表中最右端的位置
实现SetPos函数的时候
我们首先要判断一下
Pos这个值
它是否属于一个合理的取值范围
如果不是的话
我们就应该返回false
接下来我们要做的事情
就是要把栅栏移动到pos位置上面去
对于链表来说
没有特别快速便捷的移动方法
我们只能够先把栅栏
先调整到链表的最前面
也就是0号位置
然后从前往后
通过next指针
逐个结点移动到pos位置上面去
总共需要发生pos次移动
这个移动的过程
可以通过一个for循环来进行实现
每循环一次
fence将会指向fence的后面一个结点
循环执行了pos次
那么在这个算法中
输入数据的规模n
它是等于链表的元素个数
平均情况下for循环执行的次数
它是n的常数倍
所以算法的时间复杂度就是Θ(n)
这个算法执行所消耗的时间
与链表的长度是密切相关的
前面我们已经学习了List的
两种基本的实现方法
数组和链表
下面我们来对比一下
它们在性能上的差别
我们可以看到在数组中
进行插入和删除元素的效率
它是比较低下的
需要Θ(n)的时间
这是因为其中涉及到了一个
数据的移动的问题
而在链表中插入 删除是非常高效的
因为我们只需要简单地去修改指针
而另外一方面
在数组中我们要将访问的位置
调整到任意位置上面去
这样的一个操作它的效率是非常高的
可以常数时间完成
这也就意味着
在数组中我们随机访问任意位置
它都可以很快地完成
但是在链表中
同样的操作它需要消耗很大的时间
需要Θ(n)的时间
这是因为在链表里面
我们只能够顺序地去访问其中的数据
此外在空间资源的分配方面
数组需要预先地去分配相应的空间资源
而链表在分配空间的时候相对灵活一些
它所需要的空间
可以灵活地随着元素的数量增长
而进行动态的增长
所以我们可以看到
数组和链表这两个数据结构
它们有非常强的差异性
选择哪种实现方式
要取决于我们实际的应用
好的 这节课我们就讲到这里
下节课我们再见
-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
