Linked Lists

Overview

Recall questions on linked lists and how they are stored, the free list, advantages and disadvantages against arrays, creating, traversing and searching a list, adding, inserting and deleting nodes in the right pointer order, and doubly linked lists.

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

   What is a linked list?

   Model answer

   A dynamic data structure made of nodes, where each node holds a data item and a pointer giving the location of the next node. A separate head (or start) pointer identifies the first node, and the last node's pointer holds a null value to mark the end. The nodes themselves do not need to be next to each other in memory.

2. 2

   How is a linked list actually stored in memory?

   Model answer

   The nodes can be scattered anywhere in memory; what holds the list together is the pointer in each node. In a procedural, array-based implementation the list is often held as two parallel arrays, or as an array of records with a data field and a next-pointer field, where the pointer is an index into the same array rather than a memory address. A second pointer, the free-list pointer, chains together the unused slots so that new nodes can be found.

3. 3

   What is the free list, and why does an array-based linked list need one?

   Model answer

   The free list is a chain of the currently unused nodes in the array, linked by their pointer fields, with its own start pointer. Because the array's slots are never actually destroyed, the implementation needs some way of knowing which are available: when a node is added it is taken from the head of the free list, and when a node is deleted it is returned to the free list. Without it, the program would have no way of finding reusable space.

4. 4

   Give two advantages of a linked list over an array.

   Model answer

   It is dynamic, so it uses only as much memory as it currently needs and can grow until memory runs out rather than being fixed at creation. Inserting or deleting in the middle needs only one or two pointers to be changed rather than shuffling every following element, which makes maintaining an ordered list much cheaper.

5. 5

   Give two disadvantages of a linked list.

   Model answer

   There is no direct access: to reach the nth item you must start at the head and follow n pointers, so access is slow compared with an array's single address calculation, and a binary search is not practical. It also uses extra memory for a pointer in every node, and the pointer manipulation is harder to program and easier to get wrong.

6. 6

   How do you create an empty linked list?

   Model answer

   Set the head pointer to null, so that it points at no node. In an array-based implementation you also build the free list by linking every slot to the next one and setting the free-list pointer to the first slot, so all space is marked as available.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.