Explore BrainMass

Tabular representation of a Linked List

The table below gives portion of a linked list. Each list entry spans two consecutive address locations - the first contains a letter of the alphabet, and the second contains a pointer to the next list entry.

Header 32
Address Contents
30 J
31 38
32 B
33 30
34 X
35 46
36 N
37 40
38 K
39 36
40 P
41 34

I need to figure how to alter the pointers in the table so that the letter N is skipped over and is no longer accessed in the list.

Then how do I replace the letter N with the letter G and alter the pointers so that the new letter appears in the list in its proper place in alphabetical order?

Please explain the logic to how you arrive at the answers.

Solution Preview

Please spend some time with this detailed response (may be, go over few times) to develop your intuition/picture about it. It is suggested that you first read only till where I have shown how the original table can be pictured in different manner that is closer to abstraction we have in mind, and then work out your response that you can later compare with the further part in this response.

In abstract concept terms, a node in this case is a tuple (value, pointer), however these abstract nodes will occupy some memory.

The given table is considering that
- Each value/pointer occupies 1 unit space in table.
- If the value member of node is at address X, then the pointer member of node is at address (X+1).

Header indicates where (i.e. at what address) to find the first node of the linked list. Every singly linked list has to have a start point via which you can traverse the linked list.

Note the table column headings - "Address" and "Contents". It is giving the layout of ...

Solution Summary

Detailed explanations (sort of a road map to the solution) support the required list modifications.