[CS61C FA20] Lecture 05.2 - C Memory Management: Linked List Example — Transcript

Full transcript

1. 0:00and welcome back now let's take a look
2. 0:03at a linked list example
3. 0:05to see more c code and actually see
4. 0:07what's going to happen so let's actually
5. 0:08play with this right now
6. 0:10so we saw structs before here's a struct
7. 0:13node
8. 0:14so if you have a linked list you have a
9. 0:16often a recursive
10. 0:17data type right so this is a node that
11. 0:19has a character
12. 0:21which is a pointer to a value which is
13. 0:23some
14. 0:24word or something is a linked list node
15. 0:26okay and
16. 0:28you also have a next pointer and then
17. 0:29next pointer is struct node star next
18. 0:32that says
19. 0:32it's a pointer to a struct node so that
20. 0:34means this could be appointed to the
21. 0:36next guy and that's to the next guy and
22. 0:38then when it's null that means you're at
23. 0:39the end of that linked list
24. 0:40beautiful right let's do a typedef
25. 0:42typedef struct node
26. 0:44star list i can now say list and what
27. 0:46that means is going to be a pointer to
28. 0:48a struct node sorry a list new returns a
29. 0:51new
30. 0:52pointer to a new guy and that's going to
31. 0:53be null so that's a simple way to make a
32. 0:55new empty list
33. 0:57here's my code add a string to an
34. 1:00existing like an existing list okay
35. 1:02so list list says capital l list
36. 1:06list means that's a pointer to one of
37. 1:08these nodes it's going to have my
38. 1:10who knows how big that is care star
39. 1:12string says this is this is the pointer
40. 1:14to the string i want to add okay
41. 1:15am i passing in the string itself just a
42. 1:17pointer to it so this is great
43. 1:18a lot of storage for the linked list a
44. 1:20lot of storage for the string these
45. 1:21pointers are very lightweight way to
46. 1:22pass it into a function
47. 1:24first line says struck node star node i
48. 1:28probably could have said
49. 1:29list here so list list node equals and
50. 1:33this probably could have said list
51. 1:35list this guy could say list malik size
52. 1:38of struck node this makes a new node
53. 1:40blue now i got a new node okay
54. 1:43and node is that new guy so let's do it
55. 1:47there's my linked list here see this
56. 1:49first guy
57. 1:50and now it points to the next guy points
58. 1:51the next side here it's only too long
59. 1:53but it's pretty cool
60. 1:55i made the new node what's the contents
61. 1:57of node remember i have two fields in
62. 1:58there i've got
63. 1:59uh i've got a value and i've got a next
64. 2:01they're both garbage they both garbage i
65. 2:03made a new struct but i don't initialize
66. 2:05them we know that right
67. 2:06but now i'm going to set the first field
68. 2:08no there's my arrow notation i mentioned
69. 2:10before you have a dot notation or error
70. 2:11notation which is a pointer based
71. 2:12so no devalue says follow that go to
72. 2:15that field for value and
73. 2:16you need to make room for the new string
74. 2:20so let's actually go forward that's
75. 2:22actually so this is
76. 2:23now i'm on this line that just finished
77. 2:26okay
78. 2:28now i need to make room for that new
79. 2:31string
80. 2:32so node value is find out how long
81. 2:35sterling means
82. 2:36how long is it but it doesn't include
83. 2:38the null
84. 2:39terminator so if it's a b c it'll say
85. 2:41three because it's only a b and c
86. 2:43but you really need a b c and the null
87. 2:45terminator so this is extra plus one you
88. 2:46always have when you kind of do these
89. 2:48mallets of strings
90. 2:49so string length of string is the abc
91. 2:51that's the three plus one for the null
92. 2:52there's the four i'm gonna reserve four
93. 2:54if i'm gonna copy abc over
94. 2:57okay and i point to that uninitialized
95. 2:59that's i'll get an uninitialized value
96. 3:02then i call stir copy star copy says
97. 3:05let's bring in that value bring it over
98. 3:07and here's my abc and there's my
99. 3:09my whoops let me do it here just so i
100. 3:11draw look right there's my backslash
101. 3:14zero as my fourth guy okay so all four
102. 3:16get copied over abc
103. 3:17and the zero get copied over so does it
104. 3:19right and you better have enough room
105. 3:20for the zero as i mentioned before okay
106. 3:21so i'm good that's not by stir copy here
107. 3:24we go let's keep running
108. 3:25node next is list watch this
109. 3:30node next is this list points to that
110. 3:32node next now shit's called sharing
111. 3:34they point to the same list okay
112. 3:37there's a node there's a node and
113. 3:39there's only three nodes now
114. 3:41but watch when i return node i'm now
115. 3:44returning
116. 3:45the head i'm returning the head
117. 3:49of the whole thing and now i've just
118. 3:51added abc
119. 3:52as the front of this list of strings
120. 3:54i've now added abc to the front of that
121. 3:56pretty cool that makes sense the only
122. 3:57thing i would change if i change again
123. 3:59this could this could have said
124. 4:00list node equals list malik size of
125. 4:02struck node but other than that
126. 4:03pretty cool code i like it nice so
127. 4:06there's again we're going to keep
128. 4:07showing you examples the c codes would
129. 4:08get more fluent with how to do this but
130. 4:09here's an example of how to work
131. 4:10with structs and pointers see the next
132. 4:12lecture