Question

The following table represents the contents of some cells in a computer's main memory along with the address of each cell represented. Note that some of the cells contain letters of the alphabet, and each such cell is followed by an empty cell. Place addresses in these empty cells so that each cell containing a letter together with the following cell form an entry in a linked list in which the letters appear in alphabetical order. (Use zero for the null pointer.) What address should the head pointer contain? $$\begin{array}{lc}\text{ Address }& \text{ Contents }\\ 0\times 11& \text{ 'C' }\\ 0\times 12& \\ 0\times 13& {}^{\prime }G\text{ ' }\\ 0\times 14& \\ 0\times 15& {}^{\prime }{E}^{\prime }\\ 0\times 16& \\ 0\times 17& {}^{\prime }B\text{ ' }\\ 0\times 18& \\ 0\times 19& \text{ 'U' }\\ 0\times 1A& \\ 0\times 1B& \text{ 'F' }\\ 0\times 1C\end{array}$$

Short answer

The head pointer should contain the address 0x17.

Step-by-step solution

Identify Letters and Corresponding Addresses

Let's list the letters in the memory to identify their addresses. These letters are: B at $0\times 17$, C at $0\times 11$, E at $0\times 15$, F at $0\times 1B$, G at $0\times 13$, and U at $0\times 19$.

Arrange Letters in Alphabetical Order

We need to arrange the letters B, C, E, F, G, and U in alphabetical order. The order is: B, C, E, F, G, U.

Assign Addresses to Form the Linked List

Each letter must point to the address of the next letter in alphabetical order. Fill in the addresses as follows:- Address $0\times 17$ (B) should point to $0\times 11$ (C). Assign $0\times 11$ to the empty cell at $0\times 18$.- Address $0\times 11$ (C) should point to $0\times 15$ (E). Assign $0\times 15$ to the empty cell at $0\times 12$.- Address $0\times 15$ (E) should point to $0\times 1B$ (F). Assign $0\times 1B$ to the empty cell at $0\times 16$.- Address $0\times 1B$ (F) should point to $0\times 13$ (G). Assign $0\times 13$ to the empty cell at $0\times 1C$.- Address $0\times 13$ (G) should point to $0\times 19$ (U). Assign $0\times 19$ to the empty cell at $0\times 14$.

Identify the Tail of the List

The last letter in the list is U, located at $0\times 19$. It should point to 0, indicating the end of the list. Assign 0 to the empty cell at $0\times 1A$.

Determine the Head Pointer

The head pointer should contain the address of the first letter in alphabetical order, which is B at $0\times 17$. Thus, the head pointer should contain the address $0\times 17$.

Key concepts

Computer Memory

Understanding how data is stored in computer memory is crucial for grasping how linked lists operate. Computer memory is typically organized in a hierarchy of memory cells. Each memory cell has a unique address and can store data, such as a character or a pointer.

• Memory cells have addresses that act like a house number, unique for each one.
• Data in memory can be individual characters, numbers, or pointers (addresses pointing to other cells).
• A pointer is particularly important for data structures, helping navigate by referencing addresses.

In the given exercise, we see memory cells storing letters (like 'B', 'C', 'E', etc.) at specified addresses. The challenge is to arrange these letters in alphabetical order using their respective addresses. This requires understanding the connection between data and memory—where the position (address) of one memory cell dictates how it's accessed through pointers.

Data Structures

Data structures are organizational systems for efficiently storing and managing data. Linked lists are a fundamental type of data structure that use pointers to connect elements. In a linked list, each element, or 'node', contains data and a reference (or pointer) to the next element in the sequence.

• Linked lists are prevalent in situations where the dataset changes frequently and dynamically.
• They provide easy insertion and deletion of elements compared to static arrays.
• Each node contains data and a pointer, which plays a critical role in data structuring.

In our exercise, each letter and an adjacent empty cell form nodes in a linked list. Arranging them requires assigning appropriate addresses to make sure each node correctly points to the next, thereby creating a path from the starting point, or 'head', through to the 'tail', the last node in the list.

Pointer Representation

Pointers in a linked list can be imagined as the glue holding various nodes together. They enable traversal from one element to the next by storing the memory address of the following node. This concept is crucial when forming the linked list data structure.

• Pointers store the address of another node, allowing navigation within the linked list.
• The last node’s pointer indicates the termination of the list by pointing to null or zero.
• The head pointer starts the chain and usually contains the address of the first node.

In the given exercise, pointers were used to create an alphabetical list of letters. Each node (letter) points to the address of the next node, with the last node pointing to null (0). The head pointer, crucial for accessing the list, contains the address of the first alphabetically ordered letter, facilitating the list traversal.