Lab #2: Linked List

Objectives

• Know how to declare and build linked lists in C.
• Know how to recognize and implement classic linked list algorithms using iterative functions.

Context and preparation: We will use linked lists (unsorted, then sorted) to represent sets of integers. The classic set operations¹ on integers will be implemented using classic iterative list algorithms.

IMPORTANT the 2 main causes of segmentation fault with linked lists: : an uninitialized list : accessing the fields of an empty cell (e.g., accessing P->val or P->next when P=NULL).

Lab Questions

All questions should be tested as you go (calls in main), as usual!

From the Lecture (Unsorted Lists)

1. Declare a linked list.
2. Write the function to create a linked list by prepending at the head.
3. Write a function to print a linked list.
4. Write a function that tests whether a linked list is sorted.
5. Write a function to delete the head cell of a linked list.
6. Write a function to deallocate a list.
7. Test the previous functions. Verify with valgrind that there are no memory leaks at runtime.

Sorted Lists

We will now maintain a sorted list without duplicates.

1. Write an algorithm to insert an integer into a list sorted in ascending order. The insertion should only be performed if the element does not already exist in the list.
2. Write a function that creates a sorted list of integers by reading from a file. The integers in the file may be negative and in any order.

Set Operations

Write functions to:

1. Test whether an arbitrary list contains no duplicates.
2. Compute the union of two sets (i.e., the union of two duplicate-free lists).
3. Compute the intersection of two sets.
4. Convert an arbitrary list into a set (remove duplicates).