LinkedLists

Intuition

The following example (MS Word) uses an array of structs to store characters in alphabetical order:

Consider a situation where we have an array that stores letters. Along with each letter, we store the position of the next letter in alphabetical order. We store these two pieces of information (the letter and index of the next letter) in a struct:

Issues in doing this are that we want our code to work in general for any letter. We also have the restriction above in that we can store at most 10 letters. In C++ we can use the new command to dynamically allocate memory for a node (that would later be deallocated using delete.) In C we would instead use malloc to allocate memory and free to deallocate it.

The handout accompanying the above example includes an example program that illustrates how instead of using an array of structs (as in the above diagrams) we can dynamically allocate structs to do the same thing.

Online Resources on Linked Lists

See the Stanford linked list page, which includes a text description of linked lists (pdf) as well as the Binky Pointer Fun video which many students find to be very helpful.

Problems

Consider how to solve the following linked list problems:

(Many of these ideas taken from cslibrary.standford.edu/105/LinkedListProblems.pdf)

    1. Count how many elements are on the list, using a function

    2. Create a list by appending rather than prepending as we've done so far

    3. Declare Node *pHead=NULL; in main(), and then pass pHead to a function that creates the list. Have a second function called from main() to print out the list elements.

    4. Delete a node from the list

    5. Add Nodes to list by prepending them to the head of the list, but delete them from the tail of the list.

    6. Display the nth node on a list

    7. Delete the entire list

    8. Push onto the front of the list, and Pop off the front of the list as well.

    9. Consider how having a permanent dummy node can simplify code that manipulates a linked list.

    10. Create function insertInOrder(), so the list is always maintained as sorted.

    11. Take an unsorted list and use insertInOrder() to make it sorted.

    12. Append list A to the end of list B

    13. Remove duplicates from a sorted list

    14. Recursively reverse a linked list

Linked list of Numbers

Create a linked list of numbers, and then find the sum of the numbers:

  1. Prepend new nodes to the front of the list using listprog.cpp For now skip the part that recursively reverses the list, as we will cover that separately below.

  2. If you want to take the code that adds a node to the list and put that code inside of a function, you will need to use a reference parameter to allow the head pointer of the list to change. See listprog3.cpp for this code.

  3. For a version that uses C++ classes instead of a struct, see listprog2.cpp

listInsert.c

Inserting numbers in ascending order into a linked list.

reverseList.cpp

Enter numbers into a linked list, then recursively reverse the list. See accompanying handout (doc).

mazeList.cpp

Code to allow moving through a maze, using a linked list to store moves.

Linked List to implement Stack and Queue

A stack is like a stack of dishes in a cafeteria, where we stack new plates onto the top of existing ones, and remove from the top as well. This can be implemented using a linked list, where we push new nodes onto the top of the stack and pop the top node on the list. See stack.cpp This is also called Last-In-First-Out (LIFO).

A queue is like a ticket line, where new people arrive at the back, and leave the line from the front. See queue.cpp This is also called First-In-First-Out (FIFO).

Linked list of Words

storeWords1.c

Storing words into an array of structs, where space is all allocated statically.

storeWords2.c

Storing words into an array of structs. Space is now allocated dynamically.

storeWords3.c

Linked list of words.

storeWords4.c

Linked list of words, storing words into the list from within a function