知識點12:單鏈接表(singly-linked lists)

At this point in the course, we've covered a lot of the basics of C. We know a lot about variables, arrays, pointers, all that good stuff.

Those are all sort of built in to see as the fundamentals, but we can do more, right? We can combine things together in interesting ways.

If we combine together some of the basics that we've already learned about pointers and structures, in particular using dynamic memory allocation with malloc, we can put these pieces together to create a new data structure-- a singly linked list we might say-- that allows us to grow and shrink a collection of values and we won't have any wasted space.

A singly linked list is comprised of nodes, nodes just being an abstract term -- it's just something I'm calling that's a kind of structure, basically, I'm? Just going to call it a node -- and this node has two members, or two fields:

What does this special node structure look like?

we can define a structure-- and type define a structure like this. tyepdef struct sllist, and then I'm using the word value here arbitrarily to indicate any data type really.

You could pass on an integer or float, you could have whatever you want. It's not restricted to just integers, or anything like that.

So value is just an arbitrary data type, and then a pointer to another node of the same type.

這一段引用講述的是關于上圖strut sllist這個臨時名稱和sllnode的關系:

Now, there's a little catch here with defining a structure when it's a self referential structure. I have to have a temporary name for my structure.

At the end of the day I clearly want to call it sll node, that's ultimately the new name part of my type definition, but I can't use sll node in the middle of this.

The reason being, I haven't created a type called sll node until I hit this final point here. Up until that point, I have to have another way to refer to this data type.

And this is a self referential data type. It;s a data type of a structure that contains a data, and a pointer to another structure of the same type.

So I need to be able to refer to this data type at least temporarily, so giving it a temporary name of struct sllist allows me to then say I want a pointer to another struct sllist, a struct sllist star, and then after I've completed the definition, I can now call this type an sll node.

So that's why you see there's a temporary name here, but a permanent name here. Sometimes you might see definitions of structure, for example, that aren't self referential, that don't have a specifier name here. It would just say typedef struct, open curly brace and then define it.

But if you're struct is self referential, as this one is, you need to specify a temporary type name. But ultimately, now that we've done this, we can just refer to these nodes, these units, as sll nodes for purposes of the rest of this video.

Now, if we're going to start using them to collect information, there's a couple of operations we need to understand and work with.

So let's go through some of these operations and how we might visualize them, talking in pseudocode code specifically.

So what make this look like visually?

And lastly, we just want to return a pointer to this node.

So we'll call it new, and will return new so it can be used in whatever function created it. So there we go, We've created a singly linked list node out of thin air, and now we have a list we can work with.


Now, let's say we already have a large chain, and we want to find something in it.

And we want a function that's going to return true or false, depending on whether a value exists in that list.

A function prototype, or declaration for that function, might look like this-- bool find, and then we want to pass in two arguments.

The first, is a pointer to the first element of the linked list. This is actually something you'll always want to keep track of, and actually might be something that you even put in a global variable.

Once you create a list, you always, always want to keep track of the very first element of the list. That way you can refer to all the other elements by just following the chain, without having to keep pointers intact to every single element. You only need to keep track of the first one if they're all chained together.

And then the second thing we're passing in again is arbitrarily some -- whatever data type we're looking for -- there is inside of hopefully one of the nodes in the list.

So what are the steps?

Well, the first thing we do is we create a transversal(橫向的) pointer pointing to the lists head.

Well, why do we do that, we already have a pointer at the lists head, why don't we just move that one around? Well, like I just said, it's really important for us to always keep track of the very first element in the list.

And so it's actually better to create a duplicate of that, and use that to move around so we never accidentally move away, or we always have a pointer at some point that is right on the first element of the list. So it's better to create a second one that we use to move.

Then we just compare whether the value field at that node is what we're looking for, and if it's not, we just move to the next node. And we keep doing that over, and over, and over, until we either find the element, or we hit null -- we've reached the end of the list and it isn't there.

This should hopefully ring a bell to you as just linear search, we're just replicating it in a singly linked list structure instead of using an array to do it.


So here's an example of a singly linked list.

This one consists of five nodes, and we have a pointer to the head of the list, which is called list.

The first thing we want to do is again, create that traversal pointer. So we have now two pointers that point to the same thing.

Now, notice here also, I didn't have to malloc any space for trav. I didn't say trav equals malloc something, that node already exists, that space in memory already exists.

So all I'm actually doing is creating another pointer to it. I'm not mallocing an additional space, just have now two pointers pointing to the same thing.

So is 2 what I'm looking for?

Well, no, so instead I'm going to move to the next one.

So basically I would say, trav equals trav next.

Is 3 what I'm looking for, no. So I continue to go through, until eventually get to 6 which is what I'm looking for based on the function call I have at the top there, and so I'm done.

Now, what if the element I'm looking for isn't in the list, is it still going to work?

Well, notice that the list here is subtly different, and this is another thing that's important with linked lists, you don't have to preserve them in any particular order.

You can if you want, but you may have already noticed that we're not keeping track of what number element we are at. And that's sort of one trade that we have with linked list verses arrays, is it we don't have random access anymore.

We can't just say, I want to go to the 0th element, or the 6th element of my array, which I can do in an array. I can't say I want to go to the 0th element, or the 6th element, or the 25th element of my linked list, there's no index associated with them. And so it doesn't really matter if we preserve our list in order.

If you want to you certainly can, but there's no reason why they need to be preserved in any order.


OK, how do we insert a new node into the linked list?

So this case, we're going to pass in two arguments, the pointer to the head of that linked list that we want to add to.

Again, that's why it's so important that we always keep track of it, because it's the only way we really have to refer to the whole list is just by a pointer to the first element.

So we want to pass in a pointer to that first element, and whatever value we want to add to the list. And eventually this function is going to return a pointer to the new head of a linked list.

What are the steps involved here?

Well, just like with create, we need to dynamically allocate space for a new node, and check to make sure we don't run out of memory, again, because we're using malloc. Then we want to populate and insert the node, so put the number, whatever val is, into the node. We want to insert the node at the beginning of the linked list.

There's a reason that I want to do this, and it might be worth taking a second to pause the video here, and think about why I would want to insert at the beginning of a linked list.

Again, I mentioned earlier that it doesn't really matter if we preserve it in any order, so maybe that's a clue.

And you saw what would happen if we wanted to-- or from just a second ago when we were going through search you could see what might happen if we were trying to insert at the end of the list. Because we don't have a pointer to the end of the list.

So the reason that I would want to insert at the beginning, is because I can do it immediately. I have a pointer at the beginning, and we'll see this in a visual in a second.

But if I want to insert at the end, I have to start at the beginning, traverse all the way to the end, and then tack it on.

So that would mean that inserting at the end of the list would become an o of n operation, going back to our discussion of computational complexity.

It'd become an o of n operation, where as the list got bigger, and bigger, and bigger, it'll become more and more difficult to tack something on at the end.

But it's always really easy to tack something on at the beginning, you're always at the beginning.

Let's visualize this, because I think it'll help.

So here's our list, it consists of four elements, a node containing 15, which points to a node containing 9, which points to a node containing 13, which points to a node containing 10, which has the null pointer as its next pointer so that's the end of the list.

So we want to insert a new node with the value 12 at the beginning of this list, what do we do?

Well, first we malloc space for the node, and then we put 12 in there.

So now we've reached a decision point, right?

We have a couple of pointers that we could move, which one should we move first? Should we make 12 point to the new head of the list -- or excuse me, should we make 12 point to the old head of the list? Or should we say that the list now begins at 12.

There's a distinction there, and we'll look at what happens with both in a second. But this leads to a great topic for sidebar, which is that one of the trickiest things with linked lists is to arrange the pointers in the correct order.

If you move things out of order, you can end up accidentally orphaning the rest of the list. And here's an example of that. So let's go with the idea of -- well, we've just created 12. We know 12 is going to be the new head of the list, and so why don't we just move the list pointer to point there.

OK, so that's good. So now where does 12 next point? I mean, visually we can see that it will point to 15, as humans it's really obvious to us.

How does the computer know? We don't have anything pointing to 15 anymore, right?

We've lost any ability to refer to 15.

We can't say new arrow next equals something, there's nothing there.

In fact, we've orphaned the rest of the list by doing so, we've accidentally broken the chain.

And we certainly don't want to do that.

So let's go back and try this again.

Maybe the right thing to do is to set 12's next pointer to the old head of the list first.

then we can move the list over.

And in fact, that is the correct order that we need to follow when we're working with singly linked list.

We always want to connect the new element into the list, before we take that kind of important step of changing where the head of the linked list is.

Again, that's such a fundamental thing, we don't want to lose track of it. So we want to make sure that everything is chained together, before we move that pointer.

And so this would be the correct order, which is to connect 12 to the list, then say that the list starts a 12. If we said the list starts at 12 and then tried to connect 12 to the list, we've already seen what happens. We lose the list by mistake.


OK, so one more thing to talk about. What if we want to get rid of an entire linked list at once?

Again, we're mallocing all this space, and so we need to free it when we're done.

So now we want to delete the entire linked list. Well, what do we want to do:

If we've reached the null pointer, we want to stop, otherwise, just delete the rest of the list and then free me.

Delete the rest of the list, and then free the current node. What does that sound like, what technique have we talked about previously does that sound like?

Delete everybody else, then come back and delete me.That's recursion, we've made the problem a little bit smaller, we're saying delete everybody else, then you can delete me.

And further down the road, that node will say, delete everybody else. But eventually we'll get to the point where the list is null,
and that's our base case.

So let's take a look at this, and how this might work. So here's our list, it's the same list we were just talking about, and there's the steps.

So we have -- and I also pulled up our stack frames illustration from our video on call stacks, and hopefully all of this together will show you what's going on.

If we reach a null pointer, stop, otherwise, delete the rest of the list, then free the current node. So right now, list-- the pointer that we're passing in to destroy points to 12.

12 is not a null pointer, so we're going to delete the rest of the list. What is deleting the rest of us involved? Well, it means making a call to destroy, saying that 15 is the beginning of the rest of the list we want to destroy.

And so the call to destroy 12 is kind of on hold. It's frozen there, waiting for the call to destroy 15, to finish its job.

Well, 15 is not a null pointer, and so it's going to say, all right, well, delete the rest of the list. The rest of the list starts at 9, and so we'll just wait until you delete all that stuff, then come back and delete me.

Well 9's going to say, well, I'm not a null pointer, so delete the rest the list from here. And so try and destroy 13.

13 says, I'm not null pointer, same thing, it passes the buck. 10 is not null pointer, 10 contains a null pointer, but 10 is not itself a null pointer right now, and so it passes the buck too.

And now list points there,

it really would point to some -- if I had more space in the image, it would point to some random space that we don't know what it is.

It's the null pointer though, the list is literally now set it's values null.

It's pointing right inside that red box. We reached a null pointer, so we can stop, and we're done. And so that purple frame is now-- at the top of stack-- that's the active frame, but it's done.

If we've reached a null pointer, stop. We don't do anything, we can't free a null pointer, we didn't malloc any space, and so we're done.

之后是一系列stack frame被減去的過程,圖片在此略:

So that function frame is destroyed, and we resume-- we pick up where we left off with the next highest one, which is this dark blue frame here.

So we pick up right where we left off. We deleted the rest of the list already, so now we're going to free the current nodes. So now we can free this node, and now we've reached the end of the function.

And so that function frame is destroyed, and we pick up at the light blue one. So it says -- I've already done -- deleting the rest of the list, so free the current node. And now the yellow frame is back on top of the stack. And so as you see, we're now destroying the list from right to left.


What would have happened, though, if we had done things the wrong way?

Just like when we tried to add an element. If we messed up the chain, if we didn't connect the pointers in the correct order, if we just freed the first element, if we just freed the head of the list, now we have no way to refer to the rest of the list.

And so we would have orphaned everything, we would have had what's called a memory leak.

So as I said, there are several operations that we need to use to work with linked list effectively.

And you may have noticed I omitted one, deleting a single element from a linked list.

The reason I did that is it's actually kind of tricky to think about how to delete a single element from a singly linked list.

We need to be able to skip over something in the list, which means we get to a point-- we want to delete this node-- but in order to make it so we don't lose any information, we need to connect that node over here.

So I probably did that wrong from a visual perspective. So we're at the beginning of our list, we're proceeding through, we want to delete this node.

If we just delete it, we've broken the chain. This node right here refers to everything else, it contains the chain from here on out.

So what we need to do actually after we get to this point, is we need to step back one, and connect this node over to this node, so we can then delete the one in the middle.

But singly linked lists don't provide us a way to go backwards.

So we need to either keep two pointers, and move them sort of off step, one behind the other as we go, or get to a point and then send another pointer through. And as you can see, it can get a little messy.

Fortunately, we have another way to resolve that, when we talk about doubly linked lists.

The End
最后編輯于
?著作權歸作者所有,轉載或內容合作請聯系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市奕短,隨后出現的幾起案子愕秫,更是在濱河造成了極大的恐慌,老刑警劉巖姥份,帶你破解...
    沈念sama閱讀 217,542評論 6 504
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件唧席,死亡現場離奇詭異钾军,居然都是意外死亡,警方通過查閱死者的電腦和手機窗怒,發(fā)現死者居然都...
    沈念sama閱讀 92,822評論 3 394
  • 文/潘曉璐 我一進店門映跟,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人扬虚,你說我怎么就攤上這事努隙。” “怎么了辜昵?”我有些...
    開封第一講書人閱讀 163,912評論 0 354
  • 文/不壞的土叔 我叫張陵荸镊,是天一觀的道長。 經常有香客問我,道長躬存,這世上最難降的妖魔是什么张惹? 我笑而不...
    開封第一講書人閱讀 58,449評論 1 293
  • 正文 為了忘掉前任,我火速辦了婚禮岭洲,結果婚禮上宛逗,老公的妹妹穿的比我還像新娘。我一直安慰自己盾剩,他們只是感情好雷激,可當我...
    茶點故事閱讀 67,500評論 6 392
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著告私,像睡著了一般屎暇。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上德挣,一...
    開封第一講書人閱讀 51,370評論 1 302
  • 那天恭垦,我揣著相機與錄音,去河邊找鬼格嗅。 笑死番挺,一個胖子當著我的面吹牛,可吹牛的內容都是我干的屯掖。 我是一名探鬼主播玄柏,決...
    沈念sama閱讀 40,193評論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼贴铜!你這毒婦竟也來了粪摘?” 一聲冷哼從身側響起,我...
    開封第一講書人閱讀 39,074評論 0 276
  • 序言:老撾萬榮一對情侶失蹤绍坝,失蹤者是張志新(化名)和其女友劉穎徘意,沒想到半個月后,有當地人在樹林里發(fā)現了一具尸體轩褐,經...
    沈念sama閱讀 45,505評論 1 314
  • 正文 獨居荒郊野嶺守林人離奇死亡椎咧,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內容為張勛視角 年9月15日...
    茶點故事閱讀 37,722評論 3 335
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現自己被綠了把介。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片勤讽。...
    茶點故事閱讀 39,841評論 1 348
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖拗踢,靈堂內的尸體忽然破棺而出脚牍,到底是詐尸還是另有隱情,我是刑警寧澤巢墅,帶...
    沈念sama閱讀 35,569評論 5 345
  • 正文 年R本政府宣布诸狭,位于F島的核電站券膀,受9級特大地震影響,放射性物質發(fā)生泄漏作谚。R本人自食惡果不足惜三娩,卻給世界環(huán)境...
    茶點故事閱讀 41,168評論 3 328
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望妹懒。 院中可真熱鬧雀监,春花似錦、人聲如沸眨唬。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,783評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽匾竿。三九已至瓦宜,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間岭妖,已是汗流浹背临庇。 一陣腳步聲響...
    開封第一講書人閱讀 32,918評論 1 269
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留昵慌,地道東北人假夺。 一個月前我還...
    沈念sama閱讀 47,962評論 2 370
  • 正文 我出身青樓,卻偏偏與公主長得像斋攀,于是被迫代替她去往敵國和親已卷。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當晚...
    茶點故事閱讀 44,781評論 2 354

推薦閱讀更多精彩內容

  • **2014真題Directions:Read the following text. Choose the be...
    又是夜半驚坐起閱讀 9,495評論 0 23
  • 以前的我們見過小心翼翼的愛淳蔼, 撕心裂肺的愛侧蘸, 放蕩不羈的愛。 最后我們成了知識豐富的理論者鹉梨,卻成為了最最無能的實踐...
    地上行者Z閱讀 242評論 0 0
  • ZooKeeper是Hadoop Ecosystem中非常重要的組件讳癌,它的主要功能是為分布式系統提供一致性協調(C...
    把愛放下會走更遠閱讀 21,769評論 1 18
  • 一 成員變量解析 二 方法解析 1 添加元素 添加元素的過程如下:(1)如果tab為null或tab長度為0 則初...
    Q南南南Q閱讀 196評論 0 1
  • 給自己一個笑臉;讓自己擁有一份坦然 給自己一個笑臉存皂;讓自己從此更加自信 給自己一個笑臉析桥;讓自己勇敢面對艱險 ...
    lucky秀_b07c閱讀 331評論 6 8