ADM-201 dump PMP dumps pdf SSCP exam materials CBAP exam sample questions

数据结构:#3 链表概述 – 译学馆
未登录,请登录后再发表信息
最新评论 (0)
播放视频

数据结构:#3 链表概述

Introduction to linked list

In this lesson, we will
在本节课 我们将
introduce you to linked list data structure
向你介绍名为链表的数据结构
In our previous lesson,
在先前的课程里
we tried to implement a dynamic list using arrays and
我们尝试了使用数组来创建动态列表
we had some issues there
这种创建方式存在一些问题
it was not most efficient in terms of memory usage, in terms of memory consumption
就内存使用和消耗方面而言 它并非最高效的方法
When we use arrays, we have some limitations
使用数组会给我们带来一些局限
To be able to understand linked list well,
为了搞清楚链表的概念
we need to understand these limitations
我们需要理解这些局限性
so i’m going to tell you a simple story
所以下面我将向你讲述一个小故事
to help you understand this
来帮助你理解
let us say this is computer’s memory
假设这是计算机的内存
and each partition here is one byte of memory
每个小隔间代表内存的一个字节
Now as we know each byte of memory
我们知道内存的每个字节
has an address
都有对应的一个地址
We are showing only a section of the memory,
在这里仅展示内存的一小部分
that’s why it is extending towards the bottom and the top
所以能看到它正朝着底部和顶部两头延伸
let’s say that address increases from bottom to top
假设地址从底端向顶端递增
so if this byte is address 200,
则如果这个字节的地址是200
the next byte would be address 201
那么下一字节的地址就是201
and next byte would be address 202 and so on
再下一字节的地址则是202 以此类推
what I want to do is
现在我要做的是
i want to draw this memory from
将内存从左到右水平排列
left to right horizontally instead of drawing it from bottom to top
而不是由底部朝顶部排列
like this
就像这样
uh… this looks better
嗯 看起来更直观了
let’s say this byte here is address 200
假设这个字节的地址是200
and as we go towards the right
当我们向右进行遍历时
the address increases, so this is like 201
地址依次递增 所以这个地址是201
and we go on like 202, 203 and so on
接着便是202 203 以此类推
it doesn’t really matter whether we show memory from bottom to top or left to right
关键并不在于我们应采用水平还是竖直方式展示
these are just logical ways to look at the memory
这些仅仅是观察内存的逻辑方式
so coming back to our story
现在回到我们的故事
Memory is a crucial resource
内存是一种极其重要的资源
and all the applications keep asking for it.
所有程序都在不断请求得到它
So, Mr. computer has given this job of managing the memory
所以计算机将管理内存的工作
to one of his components, to one of his guys
交给了它的其中一个组成部分
who he calls the memory manager
我们称其为内存管理器
now this guy keeps track of
这个家伙能够探测
what part of the memory is free and what part of the memory is allocated
内存的哪些部分是闲置的 哪些部分是已被分配的
and anyone who needs memory to store something
凡是需要内存来进行存储的程序
needs to talk to this guy
都要跟这个家伙报备
Albert is our programmer
Albert是我们的程序员
and he is building an application
他正在创建一个程序
he needs to store some data
他需要在内存中存储一些数据
in the memory, so he needs to talk to the memory manager
所以他需要跟内存管理器沟通
He can talk to the memory manager in a high level language like C, let us say
他可以使用像c语言在内的高级语言进行沟通
he is using
假设他使用的是
C to talk to the memory manager
c语言和内存管理器交流
First he wants to store an integer in the memory
首先他打算在内存中存储一个整数
so he communicates this to memory manager by declaring
所以他通过声明一个整型变量
an integer variable
将请求传达给内存管理器
something like this
就像这样
the memory manager sees this declaration and
内存管理器看到声明后
he’s says that ok
就跟他说没问题
you need to store an integer variable
你需要存储一个整型变量
so i need to give you four bytes of memory
那我就给你内存中的4个字节
because integer variable is stored
因为在典型架构中 整型变量
in four bytes in a typical architecture.
以4字节为单位进行存储
and let us say in this architecture, it is stored in four bytes
假设它在此架构中以4字节为单位存储
so the memory manager looks for
那么内存管理器便在内存中
four bites of free space in the memory
寻找可用的4个字节
and assigns it or allocates it for valuable x
并将其分配给变量x
Address of a block of memory is the address of the first byte in the memory
一个内存块的地址便是块中首字节的地址
so let us say this first byte of memory here is at address 217, so
假设这个内存块中首字节的地址是217
variable x is at address 217
那么变量x的地址便是217
so memory manager kind of communicates it back to Albert that hey I have
所以内存管理器将它返回给Albert
assigned address 217 for your variable x
将地址217分配给你的变量x
you can store whatever you want there.
你可以在里面存储任何事物
and Albert can fill-in any data into this valuable
Albert能将任何数据装入变量中
now albert needs to store a list of integers, a list of numbers
现在Albert需要存储一列整数 一列数字
and he thinks that the maximum number of integers in this list will be 4.
并且他觉得数列元素的数量上限是4
so he asks the memory manager
所以他向内存管理器请求
for an integer array of size four names ‘A’
一个长度为4的整型数组‘A’
Now, arrays is always stored in memory as one contiguous block of memory.
数组总是以连续的内存块存储在内存中
So memory manager is like ok,
所以内存管理器同意请求
i need to look for a block of memory of 16 bytes for this variable this array A.
开始给数组变量A寻找16字节的内存块
so the memory manager allocates this block starting address two zero one and
所以内存管理器将这个起始地址为201
ending address two one six for this variable ‘A’
和尾地址为216的内存块分配给变量‘A’
which is an array of four integers.
这就是具有4个整数的数组
uh… because array is stored as one contiguous block of memory
因为数组以一个连续的内存块存储
and memory manager conveys the starting address of this block
而且内存管理器传递了这个块的起始地址
whenever Albert tries to access any of the elements in the array
所以当Albert尝试访问数组的任一元素时
Let’s say he tries to access,
假设他尝试访问
let’s say he tries to write the value at the fourth element in the array.
对数组的第四个元素A[3]进行写操作
which he accesses as A[3], Albert’s application knows where to write this particular
应用程序便能知道从何处写入这个特定值
value because it knows the base address
因为它知道基址
the starting address of the block ‘A’ the array ‘A’
即块’A’或者说数组’A’的起始地址
and from base address using the index which is 3 here
通过基址 根据对应值为3的索引
it calculates the address of A[3]
就能计算出A[3]的地址
so it knows that A[3] is at address two one three. So, to
所以能够知道A[3]的地址是213
access any of the elements in the array
所以 不论访问数组的哪一元素
the application takes constant time
程序总是占用恒定的时间
and this is one awesome thing about arrays that irrespective of the size of the arrays
在不考虑数组大小的情况下这是很棒的事情
uh… the application, an application can access any of the elements in an array in constant time
程序能在恒定时间内访问数组中的任一元素
now let’s say Albert uses this array of 4 integers to
假设Albert使用带有4个整数的数组
store his list
来存储这个列表
so i’ll fill in some values here at these positions, let’s say this is 8
现在将一些值放到这些位置 就比如这里是8
this is 2, this is 6, this is 5, this is 4
这是2 这是6 这是5 这里则是4
Now Albert at some point feels that ok, i need to
现在Albert突发奇想
have one more element in this list
打算给列表新增一个元素
now he has declared an array of size four
他已经声明了一个长度为4的数组
and he wants to add a fifith element in the array
现在他想在数组中加入第5个元素
so he asks
所以他向内存管理器
the memory manager that hey i want to extend my array ‘A’
请求说我想要扩展数组’A’
is it possible to do so
这样做是有可能的吗
i want to extend the same block
我想对同一个内存块进行扩展
and the memory manager is like
内存管理器回答说
when i allocate memory for an array,
当我为数组分配内存时
I do not expect that you will expect an extension, so
并没有意料到你会想要进行扩展
i use whatever memory available adjacent to that block
所以我就把与你那块相邻的可用内存块
for other variables
分配给了其它变量
in some cases I may extend the same block, but
在某些情况下 我也许能够扩展
in this case, I have an element a variable ‘x’
但现在我有一个元素或者说一个变量’x’
next to your block.
与你的内存块相邻
So, i cannot give you an extension
所以我不能给你扩展
so Albert is like what all options do i have
Albert则问我还有什么选择吗
Memory manager is like, you can tell me the new size and I can recreate a
内存管理器说你可以告诉我新的数组长度
new block at some new address
然后我在某个新的地址上重建内存块
and we will have to copy all the elements from the previous block to the
这样我们得从原先块中复制所有的元素
new block
到新的内存块中
so Albert says that ok, let’s do it
Albert说可以接受 那就做吧
but the memory manager is like
但内存管理器则又说
you still need to give me the size of the new block
你需要告诉我新内存块的大小
Albert thinks that this time he will give a really
Albert认为这次他应该给
large size for the new array or the new block.
新内存块或新数组分配很大的空间
so that it does not fill up.
所以它不会被填满
this new block starting address 224 is allocated
新内存块的起始地址被分配到了224
Albert asks memory manager to free the previous block.
Albert请求内存管理器释放先前的内存块
and this is some cost. He has to copy all the elements, all the numbers from
这是不小的开销 他必须全盘复制先前块中的元素
the previous block into the new block
到新内存块中
and now he can add one more element to this list
现在他可以给这数列添加一个新的元素
and he has kept his array large this time
他还必须保持数组的容量足够大
just in case he needs more numbers in the list
防止数列需要添加更多的元素
The only option that Albert
这样Albert仅有的选择
had was to create
便是创建一个全新的
‘A’ as an entirely new block, as an entirely new array
内存块或数组‘A’
and albert is it still feeling bad because if the list is too small
但Albert还是很郁闷 因为如果数列太短
he is not using some part of the array
数组的未使用部分就闲置了
and so memory is getting wasted
内存因此被浪费
and if the list again grows too much he will again have to
而且如果数列扩充速度太快 那么他又只能
create a new array, a new block and he will again have to copy all the elements
重建一个新的数组 新内存块 又得从先前块中
from the previous block into the new block
全盘复制所有元素到新内存块中
Albert is desperately seeking a solution to this problem
Albert渴望寻找一种解决方法
and the solution to this problem
而解决这个问题的关键就是
is a data structure named linked list
一种叫做链表的数据结构
so let us not try to understand
我们先不阐述链表的含义
linked list data structure and see how it solves
而先看看它究竟如何解决
Albert’s problem
Albert的问题
what Albert can do is that
Albert现在要做的
instead of asking the memory manager for an array
并非向内存管理器申请数组
which will be one large contiguous block of memory
因为数组会占用掉一大块连续的内存
he can ask memory for one unit of data at a time
在一个独立的请求中
for one element at a time
他向内存一次请求一个数据单元
in a separate request
来存储一个元素
I’m cleaning up the memory here
我先清理一下这里的内存
once again let’s say Albert wants to store
重新假设Albert打算在内存中
this list of four integers in the memory
存储一个包含4个整数的数列
what if he requests memory for one integer at a time.
假如他一次请求一个整数的内存空间
So, first he pings memory manager for
所以首先他向内存管理器请求
some memory to store number six
一些内存来存储数字6
memory manager will be like ok you need space to store an integer
内存管理器说可以 你需要空间存储一个整数
so you get this block of four bytes at address 204
所以你得到了地址为204的4字节内存块
so Albert can store number six here
所以Albert能在这里存储数字6
now Albert makes another request a separate request
现在Albert想另外独立地请求
for number five
数字5的存储空间
let’s say he gets this blocks starting address two one seven for number five
假设他给数字5拿到了起始地址为207的内存块
because he makes a separate request, he may or may not get
因为他做的是独立请求 他可能拿到的不是
memory adjacent to number 6.
邻近数字6所在地址的内存块
higher probability is that he will not get an adjacent memory location
他更可能没有拿到邻近的内存地址
so similarly Albert makes uh… separate
所以类似的 Albert给数字4和2
requests for number four and two
做的也是独立请求
so let’s say he gets these two blocks
假设他为数字4和2请求
at address 232 and 242 respectively four and two
得到了分别以232和242为首地址的两个内存块
so as you can see when Albert makes separate request for each integer
所以由此可知当Albert为每个整数独立请求时
instead of getting one contiguous block of memory,
并没有得到一个连续完整的内存块
he gets these disjoint non-contiguous blocks of memory
而是一些不连续也不相邻的内存块
so we need to store some more information here
所以我们需要给它们存储一些额外信息
we need to store the information that
我们需要存储信息来说明
this is the first element in the list
这是数列的第一个元素
and this is the second element in the list
这是数列的第二个元素
so we need to link these blocks together somehow
我们需要以某种方式连接这些内存块
without array, it was very simple
不能用数组 虽然它很简单
we had one contiguous block of memory, so
因为数组在内存中就是个连续的内存块
so we knew where a particular element
所以可以根据对应内存块的首地址
is by calculating its address using the
以及元素在数列中的位置
starting address of the blocks and the position of the element in the array
来计算出数组中一个特定元素的地址
but here, we need to store the information that
但在这里我们需要存放信息来说明
this is the first block which stores the first element
这是存放第一个元素的第一个内存块
and this is the second block which stores the second element
这是存放第二个元素的第二个内存块
and so on
以此类推
to link these blocks together
要想连接这些内存块
and to store the information that this is
存储能够说明这是数列中
the first block in the list and this is the second block in the list
第一个还是第二个元素之类的信息
what we can do is that
我们要做的是
we can store some extra information with each block
在每个内存块中存储额外的一些信息
so what if we can have two parts in each block something like this
假如每个内存块包含两个部分 就像这样
and in one part of the block, we store the data or the value
一个部分用来存储数据元素的值
and in the other part of the block we store the address of the next block.
另一个部分则用来存储下一内存块的地址
in this example in the first block the address part
在本例中 第一个内存块的地址部分是207
would be 217, the address of the next block that stores 5
即存放着数字5的下一内存块地址
and in this
而在这里
next block or the second block address part would be 232
第二个内存块的地址部分则是232
In the block at address 232
在地址为232的内存块中
We will store the address 242
地址部分存放着242
the address of the next block that stores number two
即存放数字2的下一内存块的地址
and the block at 242 is the last block.
地址为242的块是最后一个内存块
there is no next block after this so in the
没有下一个内存块
address part we can have
所以地址部分是0
address as zero, zero is invalid address
0是无效地址
zero can be used to mark that this is the end of the list
0能用来标记这是数列的末尾
there is no link to the next
表示在这个特定块后
uh… node or next block after this particular block
没有下一内存块或结点与它连接
so Albert now actually has to request
所以实际上Albert现在必须
memory manager for a block of memory that will store
请求内存管理器提供一个内存块来
two variables
存储两个变量
one an integer variable that will store the value of our element
其中一个整型变量用来存储元素的值
and one a pointer variable that will store
另一个指针变量则用来存储
the address of the next block the next node in the list
数列下一结点所在的下一内存块的地址
in c he can define
他可以用c语言定义
a type named Node
一个叫做Node(结点)的类型
like this
就像这样
he will have two fields in the node, one to store the data
这个结点会有两个区域 一个用来存储数据
this field will be an ineteger
这个区域就是存放一个整数
and one more field to store the address of the next node on the list
另一个区域用来存放数列下一结点的地址
so Albert will ask a Node
所以Albert要请求一个结点
Albert will ask memory for a node from the memory manager
于是便向内存管理器为结点请求内存空间
and the memory manager will be like, Ok
内存管理器觉得可以
you need a node that needs 4 bytes for
你需要4字节存储一个整型变量
an integer variable and four more bytes for
还需要额外的4字节用来存储
the pointer variable that will store the address
存放着地址的指针变量
Pointer variable also in a typical architecture is stored in four bytes
指针变量在典型架构中也是以4字节为单位存储
so now memory manager gives us a block of 8 bytes.
现在内存管理器给我们提供了8字节的内存块
and we call this block – a Node
我们称这个内存块为一个Node结点
Notice that the second field in the node structure is Node star which means
注意结点的第二块区域存放的是*Node
pointer to node
即指向结点的指针
so this field will only
所以这块区域只能用来
store an address of the next node in the list
存放数列中下一结点的地址
so if we store the list like this in the memory as these non-contiguous
如果我们在内存中用不相邻但能够彼此连接
nodes connected to each other
的形式来存储数列 就像这样
but then this is a linked list data structure
这便就是链表的数据结构
Logical view of the linked list data structure will be something like this
链表的数据结构从逻辑上看就像这样
data is stored in these nodes
数据被存储在这些结点中
and each node stores the data as well as the link to the next node
每个结点除了数值还存储着指向下一结点的指针
so each node kind of points to the next node
所以每个结点能够指向下一结点
the first node is also called the head node
第一个结点也被称为头结点
and the only information about the list that we keep all the time is
数列唯一能一直保存的信息就是
address of the head node
头结点的地址
or address of the first node
或者说第一个结点的地址
so address of the head node kind of gives us access to the complete list
所以头结点的地址使得我们能够访问整个数列
the address in the last node is NULL or zero
最后一个结点的地址是NULL或者0
which means that
也就是说
the last node does not point to any other node.
最后一个结点并不指向其它任何结点
now if we want to traverse the linked list
现在如果我们想遍历这个链表
the only way to do it is we start at the head
唯一的方法是从头结点开始
we go to the first guy and then we ask the first guy the address the next guy
我们向第一个家伙询问下一个家伙的地址
adress of the next node and then we go to the next node and ask
即下个结点的地址 接着又向下一结点
the address of the next node
请求再下一结点的地址
and this is the only way to access the elements in the linked list
这是访问链表元素的唯一方法
if we want to insert a node in the linked list
如果我们要在链表中插入一个结点
let’s say we want to add number three at the end of the linked list
假设我们要在链表的末尾添加数字3
then all we need to do is first create a node in the linked list
我们首先需要在链表中创建一个结点
sorry first … create a node independently and separately it will get
创建一个独立且不相关的结点
some memory location
它会有相应的内存地址
so we created this node with value 3. Now all we need to do
所以我们创建了值为3的结点 现在我们需要
is fill the address properly, adjust these links properly
正确地填入地址 使它们连接起来
so the address of this particular node
所以这个特定结点的地址
will be filled in this node
会被填入值为2的结点中
with value 2. And this node the address part can be NULL,
而且这个结点的地址部分是NULL
so it is the last node, it does not point to any other node
因为它是最后一个结点 不指向任何其它结点
let’s also show this uh… these nodes in the memory here
我们展示一下内存中的这些结点
so i have written the address of each node in
我已经用棕色在每个结点的上方
brown at top of these notes
写下了它们对应的地址
and i have also filled in this address field of each node
我也填写好了每个结点的地址域
let’s say uh…
我们可以说
the Node for value three gets address 252
数值为3的结点所在的地址为252
so this is how things will be in the memory and this is how the logical view
这就是事物在内存中运作的方式
will be the linked list
也是从逻辑角度看待链表能够
uh… is always identified by the address of the first node
被头结点的地址标识鉴别的方式
and unlike arrays
与数组不同
we cannot access any of the elements in constant time
我们不能在恒定的时间内访问任一元素
in the case of arrays using the
在使用数组时 可以根据
starting address of the block of memory and using the position of the
内存块的起始地址和元素在数列中的位置
element in the list, we could calculate the address of the element
来计算出元素所在的地址
but in this case we have to start at the head
但在链表中我们必须从头结点开始
and we have to ask this element for the next element
向当前元素查询下一元素的地址
and then ask the next element who is your next,
再向下一元素查询后边元素的地址
it’s like playing treasure hunt.
就像寻宝游戏
You go to the first guy and then you get the address for the
你找到第一个家伙 得到了第二个家伙的地址
second and then you go to the second guy and you get address of the third guy.
然后再去找第二个家伙询问第三个家伙的地址
so the time taken to access elements
所以访问元素所消耗的时间
will be proportional to the size of the list
与数列的长度呈正比关系
let’s say the size of the list is n,
假设数列的大小为n
there are n elements in the list
在数列中存在n个元素
in the worst case to traverse the last element we will
在最坏的情况下 访问最后一个元素
go through all the elements,
需要遍历所有元素
so time taken to access elements is proportional to n
所以访问时间与n成正比关系
or in other words we say that this operation will cost us or rather the
换句话说 这个操作的时间消耗或时间复杂度
time complexity of this operation is big-oh of n insertion into the list
相当于插入n个元素到数列中
we can insert anywhere in the list,
我们可以在数列任意位置插入元素
we first need to create a node
我们首先需要创建一个结点
and just adjust these links properly,
然后恰当的进行连接即可
like say i want 10 at 3rd position in the list
比如说在数列第3个位置插入10
so all we need to do is create a Node, store
我们需要创建一个结点
the value 10 in the data part
在其数据部分存储数值10
something like this
就像这样
Let’s say we get the node at address 310
假设这个结点的地址为310
So, we will adjust the address field in the second node
我们现在调整第二个结点的地址区域
to point to this node at address 310,
使其指向地址为310的结点
and this node will point to the node with value 4.
接着需要使这个结点指向数值为4的结点
Now to insert also, we will have to traverse the list and got to that
插入操作也需要我们遍历整个数列
particular position
才能到达特定的位置
and so this will be O(n) again in terms of of time complexity
所以它的时间复杂度也将会是O(n)
the only thing is that uh… the insertion will be a simple operation,
唯一的区别在于插入是简单的操作
we will not have to do all the shifts as
我们无需像数组那样
we had to do in an array.
做大量的元素移动
To insert something in between,
为了在两者间插入元素
we had to shift all the elements by one position
我们必须把所有元素一个个地
towards higher indices
挪到更后的位置
similarly to delete something
数列元素的删除操作与之相似
from this list will also O(n)
时间复杂度也是O(n)
so we can see some good things about linked list
我们可以看到链表的一些优点
that is no extra use of memory
因为一些内存没有被使用
in the sense that some memory is unused
所以内存不会产生额外的消耗
We are using some extra memory, we are using some extra money to store the addresses
虽然要使用额外的一些内存来存储地址
but we have the benefit that we create nodes as and when
但当我们想要插入或释放结点时
we want and we can also free the nodes as and when we want
它能够带来显而易见的好处
we do not have to guess the size of the list beforehand like in the case of arrays
我们还无需像数组那样要事先估测数列长度
We will discuss all the operations on linked list and the cost of these operations
在下节课 我们将讨论链表的所有操作和其消耗
as well as comparison with array
以及链表和数组的区别
in our next lessons. We will also be implementing linked list in C or C++
我们还会通过C或C++来创建链表
so this is all for a basic introduction to linked list
以上便是关于链表结构的基本介绍
Thanks for watching !
感谢观看!

发表评论

译制信息
视频概述

本视频我们将学习一种叫做链表的数据结构,通过介绍链表的相关操作和其时间消耗,让你对以链表为形式的数据存储能够有更深刻的理解和掌握。

听录译者

收集自网络

翻译译者

白抹灰

审核员

审核员1024

视频来源

https://www.youtube.com/watch?v=NobHlGUjV3g

相关推荐