Basic Linked List Exercises: Pointing to the nodes

Imagine that we are implementing the List ADT but this time using a linked list. Since linked lists consist of nodes, we would like an ADT that represents a single node. We could use a class such as:

class Node {
public:
    int data;
    Node* next;
    Node(int d, Node *n = NULL): data(d), next(n) {}
};

The class Node contains:

• data: a data member that will hold the value stored in that node.
• next: a pointer to the next Node in the linked list
• Node: a constructor which can receive one or two arguments. If it receives one argument, then the next will be assigned the value NULL. Notice this function is implemented directly inside the class declaration, hence the : data(d), next(n) {}.

The following statements would point the pointer a to a dynamically reserved Node that contains 10, and would point b to a dynamically reserved Node that contains 5, as shown in figure 1.

Node *a = new Node(10);
Node *b = new Node(5);

Figure 1. The two pointers and their pointer nodes.

The following statement would make the next pointer in the node that contains 10 to point to the node that contains 5, as shown in figure 2.

a->next = b;

Figure 2. After changing the next field of the node pointed to by a (yes, that funny-looking symbol is an a)

Exercises

Using diagrams similar to the previous, draw the final state of the following code examples. Imagine that we start each code sample afresh. You will turn in your diagrams on Wednesday.

Exercise 0a:

Node *a = new Node(10);
Node *b = new Node(5,a);

Figure 3. Diagram for Exercise 0a

Exercise 0b:

Node *a = new Node(10, new Node(15));

Figure 4. Diagram for Exercise 0b

Exercise 1:

Node *a = new Node(10);
Node *b = new Node(42);
Node *c = new Node(84);
c->next = a;
a->next = b;
b->next = a;

Exercise 2:

Node *a = new Node(10);
Node *b = new Node(42);
Node *c = new Node(84);
c->next = a;
b->next = a;

Exercise 3

Node *a = new Node(10);
Node *b = new Node(42);
Node *c = new Node(84);
Node *head = a;
a->next = b;
b->next = c;
Node *p = head;
p = p->next;