Lab: Linked lists - insert and delete

The other basic operations

We'll be working today with insert and delete from a linked list. These are a nice step up from print/find and append. Same concepts, but a bit more pointer management.

Check-out the following (empty) folder to work in.

https://cssvn.utrgv.edu/svn_etomai/201720_2380/lab03_insert_delete/<your username>

Commit your work at the end of lab for lab credit!

Keep makin' that list

Start by copying over your working node class and functions from lab02. In main, uses your append function to create a new list with the items "conquest", "war" and "death". Use your print function to show that it works.

Insert here

Now you're going to write a function to insert a new node into the list at any position. Before you do anything else, get out a piece of paper and follow these steps:

  1. Draw the list you made
  2. Draw a new node with the value "famine" below the list (Keep in mind that every node must have something pointing at it at all times! What's pointing at this new one?)
  3. Rearrange the pointers to insert "famine" at position 2 (between "war" and "death")

That's the general case, and it should give you an idea where you need to stop the traversal and what to do when you get there. Pay attention to the order of operations, and any need for temporary pointers to get the job done.

Your insert function will have a lot in common with append. It should take a node pointer to a list, a value to insert, and the numeric position to insert at (start with zero, like array positions). If the position is greater or equal to the length of the list, just append to the end. Here's the algorithm for the general case (don't worry about insert at 0 just yet):

  1. traverse the list until one of two conditions is true:
    • moved (position - 1) steps or
    • reach the last node in the list
  2. create a new node with the specified value
  3. modify the links to insert it into the list (refer to your drawing)

Try it out, use the debugger to check inserts at different points in the list. Put tests in main that check the general case (middle of the list) and the end-of-the-list case.

The other two cases, empty list and position 0, may require some more work. Add tests and make them work as well.

I take it back

Next up: delete! Take your drawing and delete the "war" node by moving links around. DO NOT SKIP THIS.

Now write a delete function that takes a node pointer to a list and a value to delete. It'll have a traversal, just like the other functions. It'll have issues when head is NULL or you're deleting the first node, just like the other function.

Add test cases in main for all the cases, and use the debugger to watch what's going on.