当前课程知识点：数据结构（Data Structures） > 2. List > 2.5 Linked list > Video
返回《数据结构（Data Structures）》慕课在线视频课程列表
返回《数据结构（Data Structures）》慕课在线视频列表
在这节课中
我将为大家讲解
List它的另外一种实现方式 链表
我们先来重新认识一下链表
基于链表实现的列表结构中
元素在内存中它是可以不连续存放的
彼此之间通过指针连接在一起
为了去实现这个结构
我们首先要定义一个数据元素的
基本存储单元
这个存储单元我们称为
在链表中的一个结点
那么每个结点包含有存储的数据元素
以及一个用来建立连接的指针
结点之间将会通过指针
依次地连成一个链状的结构
也就形成了所谓的链表
在这个例子中
链表最后一个元素是e4
这个结点的指针通常被设置为空指针
用来去表示链表的结束
在这个图中我们用一条斜线
来去表示这个特殊的空指针
下面我们来看一下如何去实现链表
首先我们要定义链表的结点类Node
这个类有一个模板参数Elem
它用来去指定链表中的
元素的数据类型
前面我们已经介绍过了
每个链表的结点它包含有两个部分
一个是数据元素
我们把它定义为类中的属性成员element
而另外一个部分
就是一个指向其他结点的指针next
这里element和next
共同构成了一个结点的核心要素
此外结点类它的构造函数是比较简单的
就是对element以及next分别进行赋值
那么基于结点类
我们可以去构造链表类LList
LList类继承了List抽象类
并且实现了相应的列表操作
我们先来看一下链表的存储结构
在链表中有几个比较特殊的位置
一个是表头 还有一个是表尾
另外还有一个就是栅栏位置
我们在LList属性成员中
相应地也去增加三个指针变量
一个是head
有里去指向链表的表头结点
一个是tail
它会指向链表的表尾结点
还有一个就是fence
指向栅栏位置前面的结点
此外我们还可以增加一个length整数变量
用它来去记录在链表中元素的个数
下面我们看一下LList它的构造函数
为了方便后面的插入删除操作的实现
在链表中我们通常会设置一个
特殊的头结点
这个头结点的主要作用
是用来去标识链表的开始位置
头结点的next指针
将会指向链表中的另一个元素
初始化的时候整个链表是空的
而链表中只有一个头结点
那么这个头结点它的next指针
我们把它设置为空指针
同时我们会让fence指针 head指针
以及tail指针
都去指向这个唯一的头结点
接下来我们来看一下
在List上面getValue操作的实现
这个操作是用来
去获取栅栏后面的元素的值
并且把它的值记录在引用参数it中
一般的情况下
我们只需要去获取fence
它的下一个结点的值就可以了
但是我们在写程序的时候一定要注意
所有可能出现的边界情况
当栅栏它是处于最末端的位置的时候
fence的后面已经没有结点了
这种情况下我们要返回false
要判断这种边界情况
我们只需要去判断一下
fence它是否和tail重叠
如果是的话就要返回false
而一般情况下
我们要访问fence后面的结点
也就是fence它的next指针
所指向的这个结点
并且把这个结点的数据元素的值element
记录在引用参数it中
然后最后我们返回就可以了
好的 我们这节课就讲到这里
下节课我们再见
-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
