SI204: Linked Lists 3 - add2back, insert

Linked Lists 3: insert after

Insert after a node

One of the nice things about a linked list is that it's pretty easy to insert new nodes anywhere you'd like. If there's a new value you've read in, you might not necessarily want to add it to the front of the list or to the back. You might, for example, want to insert it in a list in a way that maintains sorted order.

Let's consider a function insert_after(val, P) that will insert a node containing value val after p so that sorted order is maintained. Here's what we need to do in pictures:

We want to add a node with `data` after `p`. We are using the following struct definition: `struct Node { double data; Node* next; };`
Create the new node we want, with the proper `data` and `next` values (drag your mouse to see the code below). Node *T = new Node; T->data = val; T->next = p->next;
Splice our new node in after the node `p` points to (drag your mouse to see the code below). p->next = T;
Done!

In summary, we can write the function as follows:


void insert_after(double val, Node* p) {  // When you call this function, make sure p is not NULL
  Node* T = new Node;
  T->data = val;
  T->next = p->next;
  p->next = T                          // if p is NULL, p->next will make your program will crash!!!
}

Adding to the back of a list

Adding to the front of our bare-bones linked lists is very natural. You have two basic cases, which really need to be handled separately:

the original list L is empty
In this case, just use add2front().
the original list L is non-empty
In this case, you will have to traverse the list in order to get to the last node, and then apply insert_after() on this last node.

Here's a nice little implementation of an add2back function that works in just this way.


#include <iostream>
#include <string>
using namespace std;

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

void add2front(string d, Node*& L);
void insert_after(string d, Node* p);
void add2back(string d, Node*& L);

int main() {
  Node* L = NULL;
  string s;
  while(cin >> s && s != ";")
    add2back(s,L);
  
  for(Node* p = L; p != NULL; p = p->next)
    cout << p->data << ' ';
  cout << endl;

  return 0;
}


void add2front(string d, Node*& L) {
  Node* T = new Node; 
  T->data = d; 
  T->next = L;
  L = T;
}

void insert_after(string d, Node* p) {
  Node* T = new Node;
  T->data = d;
  T->next = p->next;
  p->next = T;
}

void add2back(string d, Node*& L) {
  if( L == NULL ) {
    add2front(d, L);
  }
  else { 
    // find the last node
    Node* last = L; 
    while(last->next != NULL)
      last = last->next;

    // insert d after the last node
    insert_after(d, last); 
  }
}

Insert in order

Suppose we want to maintain a sorted list. Using add2front and insert_after, we can easily write a function insertinorder(val,L) that will insert a new value val into L so that sorted order is maintained. There are two cases to consider when we write the function:

Case 1: Place a new node with val to the front of the list.
Case 2: Place a new node with val after some node in the list.

Case 1?

When is case 1 true? We have two sub-cases:

When the list is empty.
The value val is smaller than any value in the list. Note we are dealing with an already-sorted list, so we can easily check this condition by comparing answer is when val is smaller than the value of the first node in the list!

In conclusion, the following code handles case 1:


if( L == NULL || val < L->data )
  add2front(val, L);

Case 2?

In this case, we just need to traverse the list to find the right node and then apply the function insert_after().

Traverse the list until you find the right node. Let p point to the currently-visited node.

You end up traversing the whole list, so p points to the last node (i.e., p->next is NULL). In this case we need to insert val after this last node p.
As in the picture below, when the value val (i.e., 9) gets smaller than p->next->data (i.e., 11) for the first time, you find the right node p.


   for(Node* p = L; p != NULL; p = p->next) {
      if( p->next == NULL || val < p->next->data ) {
        insert_after(data, p);
        break;
      }
   }

Final code


void insertinorder(double val, Node*& L) {
  if( L == NULL || val < L->data ) {
    add2front(val, L);
  }
  else {
    for(Node* p = L; p != NULL; p = p->next) {
      if( p->next == NULL || val < p->next->data ) {
        insert_after(val, p); 
        break;
      }
    }
  }
}

Sorting

With our insertinorder we can sort stuff pretty easily with linked lists. For example, if you want to read in a bunch of values and put them in sorted order, you can simply put them in a list as you read them using insertinorder, and when you're done, you'll have a sorted list of values. Not bad, eh?

Suppose that you already have a list and it's not in sorted order. You could easily create a sorted copy of the list by moving through you list a node at a time and calling insertinorder for that node's data.


Node* sortedcopy(Node* L) {
  Node* S = NULL;
  for(Node* p = L; p != NULL; p = p->next)
    insertinorder(p->data,S);
  return S;
}

This function returns a copy of the original list in sorted order.

Problems

Write a program that reads in commands from the user, which are quit, add x, and print. Each time the add x command is given, the actual number (as opposed to x) is stored. Each time the print command is given, all the numbers added thus far are printed out in sorted order. I'll leave it to you to guess what the quit command does!
Modify the insertinorder function from above so that duplicate values are not inserted, but rather simply ignored. Thus, if used on the example code in which words are entered, only unique words would appear — no duplicates.
Write a program that reads in a collection of words (comma-separated, semicolon-terminated) and then prints out each word (order not important) along with the number of times that word was entered. Here's a sample run:
```
~/$ ./prog
hi , bye , yo , ciao , hi , hallo , yo , sianara ;
sinara 1
hallo 1
ciao 1
yo 2
bye 1
hi 2
```