Practice on Linked Lists

We consider the following scenario as shown in ex.cpp:


int main()
{
  // Get ints and store (in order) in list!
  cout << "Enter integers ending with a negative number" << endl;
  int n;

  Node* A = NULL;
  while(cin >> n && n >= 0)
    A = add2back(n,A);

  // print results
  printlist(A);
  cout << endl;


  // now what ?

  return 0;
}

Problem 0

Do you remember how to write add2back recursively?

Problem 1

We would like to remove a node that q points to, so that the list looks like

 ... 10, 20, 40, ...

Give the code performing the task.

Answer

Problem 2

We would like to add a node with value 25, so that the list looks like

 ... 10, 20, 25, 30, 40 ...

Give the code performing the task.

Answer

Problem 3

Write the following function in two ways (i.e., iteratively and recursively):

Node* find(int val, Node* L);

For example, suppose that the list looks as follows:

find(30, L) should return the pointer to the node with value 30.
If the list doesn't contain -12375, find(-12375, L) should return NULL.

Answers

Problem 4

Write the following function iteratively:

void find(int val, Node* L, Node*& p, Node*& q);

find(30, L, p, q) give two pointers p and q as in the above picture. In other words, pointer q points to a node having 30, and pointer p points to its previous node.
If the list doesn't contain -12375, find(-12375, L, p, q) will set q to be NULL (we don't care about p in this case).
If the first node is a match, set p to be NULL.

Answer.

Problem 5

Write a function that creates a new list containing the copy of the input list.

Node* copy(Node* L);

For example, suppose that the following code is executed.

Node* M = copy(L);

What's on the left in the table below should be the correct result.

correct	wrong

Note

Add the following code and check if valgrind says "no error".


  // right after "now what?" in main()
  Node* M = copy(A);
  printlist(M);
  cout << endl;

  // now what ?
  deletelist(A);
  deletelist(M);