Lab 7: Linked List program comparisons

Previously in CS 141 you should have worked with linked lists. Likely you worked with code to prepend nodes, perhaps to append nodes, to display the values stored on a list, to find the length of the list, to delete a node, and to insert in order.

If you do not feel comfortable jumping right in to write linked list code, refresh your understanding of the concepts using the following:

  • See Nick Parlante's Linked List Basics tutorial (and if you want some practice, the accompanying Linked List Problems).

  • See the CS 141 lecture notes on Linked Lists (LL) from Fall 2021 from Reed or Kidane:

      • 11-17 Basic building a LL using prepend

      • 11-19 Has list of many possible LL operations; Display List

      • 11-24 Delete all nodes on a LL; Append to the end of a LL

      • 11-29 Delete some node from a LL

      • 12-02 Insert in-order into a LL

      • 12-03 Use a LL to implement a Stack

  • Read sections 17.1 and 17.2 of Walter Savitch's Book "Absolute C++", 5th edition, which is available in Piazza here. While that reading is officially implemented in C++, the concepts apply to what we are doing.

Reading Outline

Your outline for this week consists of writing a small linked list program. Use Replit program linkedListAppend.c as your starting point. It currently has in it a copy of the linked list code used to prepend new nodes to the front of a list, as shown below in linkedListPrepend.c. Change the program so that it not only has a pHead pointer, but also has a pTail pointer, using pTail to append new nodes at the end of the list.

Test your program to make sure it works correctly! For instance, what happens if you add a node, then delete it, then add a different node? Does it work properly?

Submit the text of this program as your outline for this week using the same Reading Outline Submission Form that we've been using each week.

Lab Assignment

  1. Compare your and your partner's solutions to linkedListAppend.c which were submitted as your outlines for this week. Do they do anything differently?

  2. Between your version and your partner's versions of linkedListAppend.c, choose one to use for the following analysis:

      1. Describe the differences in code between the original linkedListPrepend.c version shown below and discussed in class, and this new linkedListAppend.c version you just selected.

      2. Which is better? Why? Which is easier to understand? Defend your answers using specific examples of code.

  3. Write a modified version of linkedListAppend.c called linkedListAppendWithSentinel.c, using the Lab project of that name in Replit. (If Replit is not working, use the starter code shown at the bottom of this page for linkedListAppendWithSentinel.c, along with the C compiler of your choice, or work online at onlinegdb.com/online_c_compiler)
    In this linked list version we will add a sentinel node on the list that is always there at the beginning of the list, with a data value of -1, but that is not displayed whenever we print the list. In other words, when the program first starts, this sentinel node is created and is always there, with additional nodes being created and deleted, without this node every being removed. Implement the following:

      1. Declare and initialize the sentinel node at the beginning of main()

      2. Implement function appendNumber( )

      3. Implement function deleteNumber( )

      4. Run the following three test cases:

  1. Three appends, then exit:
    a 2
    a 4
    a 6
    x

  2. Two appends, two deletes, then 2 more appends, then exit
    a 2
    a 4
    d
    d
    a 3
    a 5
    x

  3. One append, delete, attempt to delete on an empty list, then two more appends, then exit
    a 6
    d
    d
    a 1
    a 2
    x

  1. Describe which parts of your program you had to change by using a sentinel in this way. What are the advantages / disadvantages of this approach, compared to the previous linkedListAppend.c version? Use specific examples of code to make your case.

  2. Time permitting (which you likely will not have time for), consider one of these:

      1. A circularly linked list, where the last node's pointer points back to the first node. What uses can you think of for this? What are the advantages / disadvantages of this implementation?

      2. A doubly linked list where each node has pointers to the nodes before it and after it. What are the advantages / disadvantages of this implementation in terms of run-time efficiency and memory required for the list?

LinkedListPrepend.c

See below for the basic linked list code starting point that prepends each new node to the front of a list. This is the same version linked above that is on Replit that you used as the starting point to modify into LinkedListAppend.c. (If you think of the list as being vertical and not horizontal, then the prependNumber() function is the equivalent of a stack push operation, and the deleteNumber() function is the same as a stack pop operation.) Below that you can find the starter code to use in lab for LinkedListAppendWithSentinel.c

LinkedListAppendWithSentinel.c

The code below for LinkedListAppendWithSentinel.c is provided here as starter code for you to use in some other environment, in case Replit is down.
(If Replit is not working use the C compiler of your choice, or work online at onlinegdb.com/online_c_compiler )