Traverse and print a linked list in forward and backward order

Given a linked list, write code to print the list in forward and backward order.

Solution:

This problem is discussed as an example in this post. A linked list is a data structure where address of next node is stored inside each node.
Structure of Node

Structure of Node of a list is as given below:

struct Node
{
  int data;
  Node* next;
};

If we are using C++ (or other Object Oriented language) than this structure may have other operations, (e.g. Constructor that initialize the node properties) as shown below.

For example, if the linked list is

1 -> 3 -> 8 -> 2 -> 9 \

Then this list actually looks like below in the memory:

head is a pointer that points to the head of the linked list. Usually all the nodes in a linked list resides on the heap memory.

struct Node
{
  int data;
  Node* next;
  // CONSTRUCTOR
  Node(){}     // DEFAULT CONSTRUCTOR
  Node(int x): data(x), next(NULL){}
};

Creating the list

For this code, we assume that there is a constructor in the structure.  Below function creates such a list and return a pointer to the head of this list.

// CREATE LIST 1 -> 3 -> 8 -> 2 -> 9
Node* createList()
{
  Node* h = new Node(1);
  h->next = new Node(3);
  h->next->next = new Node(8);
  h->next->next->next = new Node(2);
  h->next->next->next->next = new Node(9);
  return h;
}

If you are using C language or you do not have the constructor inside the structure, we can write a separate function to create one node. This function will allocate memory and initialize the node as shown below:

Node* createNode(int x)
{
  // CREATING THE NODE (ON HEAP)
  struct Node* h = (struct Node*)malloc(sizeof(struct Node));
  // INITIALIZING THE NODE
  h->data = x;
  h->next = NULL;
  return h;
}

If the are using this function, then the createList function will be as below:

// CREATE LIST 1 -> 3 -> 8 -> 2 -> 9
Node* createList()
{
  Node* h = createNode(1);
  h->next = createNode(3);
  h->next->next = createNode(8);
  h->next->next->next = createNode(2);
  h->next->next->next->next = createNode(9);
  return h;
}

Note that we are using a separate function only because of convenience, else each node can be created and initialize inside createList function itself, but it may not look that neat.

Printing the list (Forward)

Printing the list requires a simple traversal of the list. Initially h is pointing to the first node of the list, print the data field of the node pointed to by h and then move h forward. Keep doing it until we hit the end of list.

void printList(Node* h)
{
  while(h != NULL)
  {
    cout << h->data << " "; h = h->next;
  }
}

Printing the list (Backward)

Printing the list backward is tricky because we cannot move backward in a singly linked list. One way of printing the list backward is to first reverse the list, then print it in forward order and then reverse it back again to restore the original list.

This may look cumbersome because we are reversing the list twice, but it is an optimal code that takes O(n) time and constant extra memory.

We have already seen the recursive and non-recursive code to reverse the linked list.

Another way is to use head recursion to traverse the linked list and print the node values while returning back in the recursion, this logic is discussed in this post.

But recursion, comes with a cost.