Introduction to Linked List

Introduction to Linked List

Introduction to Linked List

Data Structures: Introduction to Linked List
Topics discussed:
1) Different ways to maintain a list in memory.
2) Types of Linked List.
3) Single Linked List.
4) Representation of Single Linked List.

C Programming Lectures: https://goo.gl/7Eh2SS

Follow Neso Academy on Instagram: @nesoacademy(https://bit.ly/2XP63OE)
Follow me on Instagram: @jaspreetedu(https://bit.ly/2YX26E5)

Contribute: http://www.nesoacademy.org/donate

Memberships: https://bit.ly/2U7YSPI

Books: http://www.nesoacademy.org/recommende…

Website ► http://www.nesoacademy.org/
Forum ► http://forum.nesoacademy.org/
Facebook ► https://goo.gl/Nt0PmB
Twitter ► https://twitter.com/nesoacademy

Music:
Axol x Alex Skrindo - You [NCS Release]

#DataStructuresByNeso #DataStructures #LinkedList #SingleLinkedList


Content

5.62 -> From this presentation onwards,
7.72 -> we are starting with the new chapter called linked list
10.24 -> and in this particular presentation, I will introduce
13.12 -> what a linked list is all about and how it looks like.
16.06 -> So let's get started.
17.82 -> Let's say our target is to arrange the name of the students
20.96 -> according to the first letter of their names.
23.44 -> This is our target.
24.84 -> We need to arrange the name of the students.
26.74 -> These are the names available with us.
28.74 -> We need to arrange them in sequential order
31.42 -> that too according to the first letter of their names.
33.8 -> And this is how the order looks like, right?
35.8 -> Of course, the first name must be Alpha.
38.56 -> Then we have John, then Mark, Michael, Rock, Smith, Tony.
42.54 -> These are the names arranged in a sequential order
45.18 -> according to the first letter of the names.
47.18 -> Now my question is, how to maintain this list in a memory?
51.06 -> That is, the actual memory.
52.6 -> In order to maintain a list in a memory,
55 -> there are basically two ways available with us.
57.36 -> The first one is of course, by using array data structure.
60.32 -> The other one is using linked list data structure.
63.42 -> By using these two ways,
65.02 -> we can maintain a list in a memory.
66.78 -> These are basically the data structures.
68.78 -> We have already dealt with array data structure.
71.2 -> Now, in this presentation and in the subsequent presentation,
74.68 -> we will deal with how to maintain
76.68 -> a list using linked list.
79 -> Arrays have some limitations and disadvantages
81.94 -> and there is no doubt about it.
83.94 -> This is very sad.
85.06 -> But we will see, how linked list overcomes
87.62 -> the limitations and disadvantages of arrays.
90.68 -> We will see, what are the disadvantages
93.32 -> and limitations of arrays and we will see
96.1 -> how linked list overcome those limitations and disadvantages
99.26 -> in the subsequent lectures.
101 -> But for now, we will see
102.86 -> what are the different types of linked list we are available with.
105.96 -> The first one is of course, single linked list.
108.66 -> This is the basic type
110.22 -> and the first type of linked list.
112.22 -> Basically, in single linked list navigation is forward only.
116.76 -> That means we can go in forward direction
118.76 -> and we can't go backwards.
120.52 -> So navigation is forward only.
122.52 -> This is the way, we can identify a linked list is a single linked list.
125.78 -> When the navigation is forward only,
127.78 -> then it is called as a single linked list.
130.42 -> But when the navigation is forward and backward,
133.32 -> then it is called a doubly linked list.
135.32 -> So here, in the doubly linked list
136.88 -> forward and backward navigation is possible.
139.86 -> We have another type called circular linked list.
143.02 -> Here, the last element is linked to the first element
146.6 -> as the name itself suggests, that is a circular linked list.
149.82 -> So definitely the last element must be linked to the first element.
153.22 -> Now, we will discuss what is a single linked list.
157.98 -> A single link list is a list made up of nodes that consists of two parts.
162.14 -> Basically, a single linked list is a list made up of nodes.
166.18 -> Now, what is a node by the way?
168.18 -> This is how a node looks like.
170.18 -> This node contains two parts.
172.06 -> The one is data, and the other one is link.
174.48 -> Data part contains the actual data
177.04 -> and link part contains the address of the next node of the list.
180.38 -> If you ask me how linked list is made,
182.84 -> I will simply give you this answer,
184.7 -> that a linked list is made up of nodes.
187.62 -> Now, we will see how to represent a single linked list.
191.2 -> Suppose we want to store a list of numbers.
193.86 -> These are the list of numbers we are available with, 23, 54, 78, and 90
198.9 -> For this purpose, I need to create four different nodes.
201.62 -> Because we have four different numbers to store,
204 -> we need to create a list of four different nodes.
206.5 -> The first node contains the data 23,
208.9 -> the second node contains the data 54,
210.9 -> third node contains the data 78,
212.9 -> and fourth node contains data 90.
215.42 -> Now, I would like to tell you that these nodes
218.06 -> need not be stored in sequential order in memory.
220.94 -> This should be well noted.
222.44 -> For the simplicity sake, I have taken these addresses.
225.46 -> The first node address is 1000,
228.1 -> second node address is 2000,
230 -> third node address is 3000,
231.82 -> and fourth node address is 4000.
233.82 -> And you can see, the addresses need not be sequential.
236.34 -> This is not an array, this is a linked list.
238.48 -> Now of course, there is something missing out here.
240.72 -> This list is incomplete.
242.38 -> Obviously, the list has not been created upto now.
245.18 -> Because, there is some way to reach the next node of the list
248.26 -> and in order to do that, we will store
250.36 -> the addresses in the link part of each and every node.
253.72 -> How it looks like, let's see.
255.44 -> These are the addresses which we will store in the link part.
258.62 -> You can see, that the first node contains this address that is 2000,
262.26 -> which is the address of the second node of the list.
264.62 -> Isn't that so?
265.78 -> From the first node, I can easily reach the next node
268.84 -> if I have this address. That is why,
271.2 -> I have stored this address over here.
273 -> From the second node, I can easily the third node.
275.48 -> Because, the address stored here is 3000,
277.3 -> which is the address of the third node of the list.
279.38 -> And third node contains the address 4000,
282.04 -> which is the address of the last node of the list.
284.42 -> And last node contains NULL, which means
286.42 -> it is not containing any address.
288.1 -> It will simply not point to anything.
290.02 -> And it indicates that this is the last node, right?
292.38 -> So basically, with the help of link part of the node,
296.16 -> we can reach the next node of the list.
298.4 -> I am representing the link between
300.4 -> these nodes using these arrows.
302.5 -> But you may ask this question that,
304.84 -> how to access the first node of the linked list?
307.56 -> If we have the address of the first node,
309.56 -> we can reach the rest of the nodes, right?
311.56 -> But, how to access the first node of the linked list?
314.22 -> In order to access the first node of the linked list,
316.52 -> we need a pointer.
318.06 -> With the help of pointer, we can access
320.24 -> the first node of the list, if it contains
322.24 -> the address of the first node.
323.94 -> I am naming this pointer as head.
326.04 -> And in the rest of the lectures, we will also see
328.3 -> that the name of this pointer will remain head.
330.68 -> Because, it is the pointer to the first node of the list.
333.36 -> By using this pointer, we can
335.34 -> access the first node of the list.
337.04 -> And from the first node, we can access the second node and so on.
340.62 -> So basically, this whole list is now accessible.
343.38 -> As this pointer contains the address 1000,
346.14 -> so I am using this arrow, which represents that
348.58 -> this pointer contains the address of the first node.
351.7 -> After seeing how a single linked list looks like,
354.46 -> we will see how to create a single linked list programmatically
357.68 -> and how to perform different operations in
359.68 -> single linked list and other linked list
362.04 -> in the same way as we do in the case of arrays.
365.5 -> Okay friends, this is it for now.
367.5 -> Thank you for watching this presentation.

Source: https://www.youtube.com/watch?v=R9PTBwOzceo