Linked lists

Overview

Recall questions on how linked lists are stored, traversal, inserting into and deleting from an ordered list, tracing an array-based list, the free space list, linked lists versus arrays, binary search on a linked list, and time complexity.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   Describe how a linked list is stored.

   Model answer

   As a set of nodes, each holding a data item and a pointer giving the location of the next node. A separate start or head pointer gives the location of the first node, and the last node's pointer holds a null value to mark the end. The nodes themselves need not be next to each other in memory, because the pointers, not the positions, define the order.

2. 2

   How do you traverse a linked list?

   Model answer

   Set a current pointer to the value of the head pointer. While the current pointer is not null, process the data held at the current node, then set the current pointer to that node's next pointer. The loop ends when the null pointer at the end of the list is reached.

3. 3

   Describe the algorithm for inserting a new node into an ordered linked list.

   Model answer

   Take a free node from the free space list and write the new data into it. Traverse the list keeping track of the previous node until you reach the node whose data is greater than the new item. Set the new node's pointer to that node, and set the previous node's pointer to the new node. If the new item belongs first, point the new node at the old first node and update the head pointer instead.

4. 4

   Describe the algorithm for deleting a node from a linked list.

   Model answer

   Traverse the list until you find the node to delete, keeping a pointer to the node before it. Copy the doomed node's next pointer into the previous node's next pointer, so the list now steps straight past it. Return the removed node to the free space list. If the node deleted was the first one, the head pointer is set to the second node instead.

5. 5

   A linked list is held in an array. Position 0 holds 12 with next 2, position 2 holds 25 with next 1, position 1 holds 40 with next null, and the head pointer is 0. What is the list in order, and where is 40 stored?

   Model answer

   The list in order is 12, 25, 40. Following the head pointer to position 0 gives 12, its next pointer sends you to position 2 for 25, and that node's next pointer sends you to position 1 for 40, whose null pointer ends the list. The value 40 is physically stored at position 1, second in memory but last in the list.

6. 6

   A linked list is held in an array: position 0 holds 12 with next 2, position 2 holds 25 with next 1, position 1 holds 40 with next null, and the head pointer is 0. Describe exactly what changes when 30 is inserted in order, using free position 3.

   Model answer

   Write 30 into position 3. Because 30 belongs between 25 and 40, position 3's next pointer is set to 1, which is where 40 lives, and position 2's next pointer is changed from 1 to 3. No data is moved, and the list now reads 12, 25, 30, 40.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.