Data Structures in C++: Linked Lists, Stacks and Queues

Hello students, welcome to Kwickprep. How does your phone remember every undo step, or a railway counter serve people in order? The answer is data structures. Today we build a linked list, a stack and a queue, learn searching and sorting, and measure speed with Big O.

Let us start with the building blocks. A data structure is simply a way to organise data so we can use it well. An array has a fixed size and needs one continuous block of memory. A linked list is instead a chain of small boxes called nodes, like coaches of a train. Each node holds some data and a pointer, which is the memory address of the next node. The last node points to nullptr, meaning nothing comes after it.

Each Node has an int named data and a pointer named next. Node c holds thirty and points to nullptr. Node b holds twenty and points to c. Node a holds ten and points to b. The loop starts a pointer at a, and keeps going while it is not null. The arrow operator reads a member through a pointer, and p equals p arrow next moves along the chain. So it prints ten, twenty, thirty.

In real programs, nodes are created while the program runs using new. Here h is the head, the pointer to the first node, and it starts empty. Each new node points to the old head, then becomes the new head. Pause and predict. We insert three, then two, then one. What prints? One two three, because each insert goes to the front. Real programs must also free nodes with delete.

Let us compare an array and a linked list. An array has a fixed size, while a linked list grows and shrinks. An array uses one block of memory, while list nodes can be anywhere. An array reaches item i directly, but a list must walk from the head. Inserting at the front of an array shifts every item, but a list only changes two pointers. A list needs extra memory for one pointer in every node.

Now the stack. A stack adds and removes items at only one end, called the top, like a pile of plates in a canteen. This rule is called LIFO, last in, first out. Push adds an item on top, and pop removes the top item. Overflow happens when you push onto a full stack. Underflow happens when you pop from an empty stack. Undo in an editor and the back button in a browser both use stacks.

Here the array st holds up to five items, and top starts at minus one, meaning empty. Push first increases top, then stores the value there. Pop returns the value at top, then decreases top. We push ten, then twenty. The first pop gives twenty, the last item in, and the next gives ten. A full program should check top before each push and pop, to catch overflow and underflow.

Next, the queue. A queue adds items at one end, the rear, and removes them from the other end, the front. This rule is called FIFO, first in, first out. Enqueue adds at the rear, and dequeue removes from the front. A railway ticket counter line is a perfect example, because whoever comes first is served first. A circular queue wraps around the array, so it can reuse spaces freed at the front.

Here enq means enqueue and deq means dequeue. Enqueue stores the value at rear, then moves rear forward. Dequeue returns the value at front, then moves front forward. We add ten, twenty and thirty. The first two dequeues give ten and twenty, in the same order they came. Pause and predict. What would a third dequeue give? Thirty.

The standard library already has both structures. The stack header gives push, pop, top and empty. The queue header gives push, pop, front and back. Careful, in both of them pop removes the item but does not return it, so read top or front first. Use these in real programs, and build your own only to learn how they work.

Now searching. Linear search checks each item one by one, from the start, until it finds the key. The key is the value we are looking for, here eighty eight. It checks forty two, then seventeen, then eighty eight at index two, and prints two. It works on any list, sorted or not, but it can be slow for a long list.

Binary search works only on sorted data, but it is much faster. Here l is the low index, h is the high index and m is the middle. First, the middle index is one, holding seventeen. Seventeen is less than forty two, so the answer must be on the right, and low becomes two. Now the middle is two, holding forty two, so it prints two. Each step throws away half of the remaining items.

Sorting means arranging items in order. Bubble sort compares each pair of neighbours and swaps them if they are in the wrong order. After the first pass, the largest value, forty, bubbles to the end. Each later pass needs one comparison less, which is why j stops at three minus i. After three passes, the array is ten, twenty, thirty, forty.

How do we compare these methods fairly? Big O notation tells how the number of steps grows as the data size, called n, grows. We usually look at the worst case, such as the key being at the very end. Constants are dropped, so two n steps is still written O of n. This lets us compare methods on paper, without depending on a fast or slow computer.

Here are the values you must know. O of one is constant time, like push and pop on a stack. O of log n is logarithmic, like binary search. O of n is linear, like linear search. O of n log n is the speed of good sorts, like std sort. O of n squared is quadratic, like bubble sort.

Let us feel the difference with one thousand items. Linear search may need one thousand checks. Binary search needs only about ten, because halving one thousand ten times leaves one item. Bubble sort needs about ten lakh steps, because one thousand times one thousand is ten lakh. That is why choosing the right method matters.

Let us revise what we learned today. A linked list is a chain of nodes, each holding data and a pointer to the next. A stack is last in, first out, with push and pop at the top. A queue is first in, first out, adding at the rear and removing from the front. Linear search works on any list, but binary search needs sorted data. Big O compares speed, from constant, through log n, n and n log n, to n squared. Try writing a function that counts the nodes in a linked list.