Linked Lists

Hello students, welcome to Kwickprep. An array needs its size fixed in advance. What if a class keeps getting new admissions all year? Today we learn the linked list, which grows one node at a time. We will see nodes and links, insertion, deletion, traversal, and compare it with an array.

Think of a treasure hunt game. Each clue has a message, and it also tells you where the next clue is hidden. A linked list works the same way, and each item is called a node. A node holds the data and a link to the next node. A variable called start remembers where the first node is. The last node links to null, which means there is no next node.

In Java, a node is an object of a class. The variable data stores the value, like roll number ten. The variable next has type Node, so it can refer to another node. In C and C plus plus this link is called a pointer, while Java calls it a reference. The constructor stores d in data and sets next to null. A class that refers to its own type in this way is called self referential.

Let us build the list ten, twenty, thirty, one link at a time. First, start refers to node one. Node one holds ten, and its next refers to node two. Node two holds twenty, and its next refers to node three. Node three holds thirty, and its next is null, so the list ends here. The nodes can be anywhere in memory, because the links join them.

Traversal means visiting every node once, from the first to the last. Here the class Ll is our node, with data d and link next. The variable h is the head, or start, of a list holding five and eight. A helper variable p starts at h. We print p dot d, then move p to p dot next. When p becomes null, the loop stops, so it prints five and eight.

Exams often ask for the traversal algorithm in steps. First, set a pointer p equal to start. Second, while p is not null, process p dot data, for example print it or count it. Third, move p to p dot next and repeat. Never move start itself, because then you lose the way back to the first node.

Now insertion, which means adding a node. To insert at the beginning, first create the new node n with data five. Then make n dot next refer to the old first node, which is start. Finally, make start refer to n. The order matters a lot. If you change start first, you lose the rest of the list.

To insert at the end, create the new node n with data forty. Then walk p from start until p dot next is null, so p is the last node. Finally, link p dot next to n. The new node's next is already null, so it becomes the new last node. This code assumes the list is not empty, and for an empty list we simply set start to n.

To insert twenty five between twenty and thirty, let p be the node holding twenty. First, make n dot next refer to p dot next, which is thirty. Then make p dot next refer to n. Now the list reads ten, twenty, twenty five, thirty. No other element moves, unlike an array.

Deletion means removing a node. To delete the first node, make start refer to the second node, which is start dot next. To delete a node in the middle, find the node p just before it. Then make p dot next skip over it, by setting it to p dot next dot next. Java's garbage collector later frees the unlinked node automatically. Before deleting, always check that the list is not empty.

Pause the video and predict the list after each step. We start with ten, twenty, thirty. After start equals start dot next, the first node is skipped, so the list is twenty, thirty. After inserting five at the beginning, the list is five, twenty, thirty. Check your answer before we move on.

This comparison comes in almost every exam. An array has a fixed size, while a linked list grows and shrinks as needed. Array elements sit side by side in memory, while nodes can be anywhere, joined by links. An array reaches any element directly by its index, but a linked list must walk from start. Inserting in an array shifts elements, while a linked list only changes links. But every node needs extra memory to store its link.

Let us revise. A node holds data and a link to the next node. Start refers to the first node, and the last link is null. Traverse with p starting at start, moving to p dot next until null. Insert and delete by changing links, and do it in the right order. A linked list gives flexible size, while an array gives direct access.