Welcome Back!

By the end of this class, you should know...

  • What is a linked list?
  • How is a linked list different from an array?
  • What are the advantages of using a linked list instead of an array?
  • What are the advantages of using an array instead of a linked list?
  • What is a node?
  • What are some of the linked list operations?


Writing your own Linked List class will give you good practice on pointers:

XKCD

Pointers

Over the next few classes we will be working a lot with pointers. Image source.

Review Activity

With a partner, answer the following questions:
    • What is an ADT? Give the two part definition.
    • What is the difference between an ADT and a Data Structure?
    • Label the following prototypes as either access function, manipulation procedure or constructor:
      • void setName(string name);
      • int getID() const;
      • Student(string name, int id);


What is a Linked List?

  • We are all familiar with lists.
  • We use lists all the time for things like grocery shopping, e.g.:
    • Bread
    • Kale
    • Chocolate
  • Or, keeping track of our assignments:
    • Physics exam Wednesday.
    • Do Calc homework tonight.
    • Read short story for English.
  • A linked list is simply a list of values that are linked together in a special way.
  • We will discuss linked lists and how they work in detail during this lesson.


Linked Lists vs Arrays

Why Not Arrays?

  • When looking to store a collection of data (e.g. phone numbers, names in a class roster, etc), your first thought might be to use an array.
  • Arrays are a fundamental language construct in C++ and as such offer a good first point of comparison.
  • However, arrays are not always the best choice to store data.
  • Can you think of any problems with arrays?
Problem 1: Arrays are of fixed size:
    • But, what if I don't know ahead of time how many elements I will be storing in an array?
    • The most common approach is to make the array capacity larger than I think I need.
const int CAPACITY = 50; //Why do I need to make CAPACITY const?
string class_roster[CAPACITY];
    • However, this approach may not always be sufficient.
    • Consider a start up company that needs to store customer records. 
    • When the company first begins operations, will it be able to predict roughly how many customers it might acquire in the future?
    • Maybe not.
    • It might be expensive to allot more room for storage of customer data than it actually needs. However, it could be even more dangerous not to allot enough.

Illustration of an array as 10 boxes numbered 0 through 9; an index of 0 indicates the first element in the array

Arrays are of fixed size because all elements are stored next to each other in contiguous memory locations. Image Source

Problem 2: Maintaining an ordered list is "expensive" with arrays:
    • For example, let's say that I create an array to store my class roster.
    • I wait until the second week to insert each student name alphabetically into the array, thinking that I now have all the student names.
    • But, what if there is a late add?
    • What do I do about students who drop?
    • If my array is already at capacity, and I add a name, I will need to create a whole new array.
    • What can I do if I am not at capacity? (Hint: Shift all names down)


Why Linked Lists?

  • Linked Lists offer two distinct advantages over arrays.
Advantage 1: Linked lists are sized dynamically:
    • In other words, you don't need to know ahead of time how many data points your list will store.
    • Unlike arrays which store all the data in contiguous memory locations, linked lists store each piece of data in a unique location somewhere in the computer memory.
    • Lists keep track of the location of each piece of data by storing pointers to the data's location in memory.
    • Therefore, unlike with arrays, there is no need to set aside a block of memory to store a list.
    • The list simply adjusts its size each time a new piece of data is added or subtracted by storing a new pointer or removing an old one.
    • We will look at how this works in a moment.


Advantage 2: Linked lists allow for ease of insertion and deletion:
    • Because of how data is stored, elements can be inserted and deleted without creating a whole new linked list.

Example showing how data is stored in a list using pointers. Image source

Advantage of Arrays

  • However, linked lists do not allow for random access.
    • In other words, we cannot directly access a specific element in the list without scrolling through the list item-by-item to find the element we are looking for.
  • Therefore, whether to use a linked list or an array is dependent on the situation. Both are important tools in your programming toolbox.



Your programming toolbox should include both arrays and linked lists


Example Linked List vs Array Diagrams:

  • Storing a list of names in an array:

  • Storing a list of names in a linked list:




How Linked Lists Work

Group Activity: Acting Out A Linked List

  • This exercise will help you understand how linked lists work, as well as learn the names of your classmates.
  • The instructor will hand out a piece of paper to each student.
  • Each piece of paper will contain some data, as well as a "pointer" to the name of another student in the class.
  • You will NOT know who has the pointer to your name. You will only know to whom you are pointing.
  • You will NOT know what data the person to whom you are pointing has. You will only know what data YOU have.
  • Additionally, two students will fill additional important roles:
  • One student will also receive a piece of paper indicating that he or she is the start of the list. This paper will have the word "start" on it. The starting node of the list tells us where the lists starts.
  • Another student will receive a piece of paper indicating that he or she is the last node of the list. This paper will have the word "stop" on it. The stop node of the list tells us where the list ends.
  • Next, we will perform a search for two pieces of data to discover which students have them.
  • Then, we will remove every other piece of data from the list.
  • Finally, we will add some new pieces of data.


The Linked List Data Structure

  • As we saw during our last activity, linked lists are a data structure where data is chained together using a series of pointers.
  • These pointers keep the list items in order.
  • Thus, a list needs to keep track of both the data items and the pointers to the next item.
  • To do so, lists are comprised of special objects called Nodes.
  • Just like the piece of paper you were handed during our group activity, a Node is an object that holds both data and a pointer to the next Node in the list.
  • Linked lists are simply chains of these Nodes.


Representation of a linked list. Notice that each node contains data and a pointer to the next node.
  • Special Nodes within the list are start, which indicates the start of the list, and stop, which indicates the end of the list. Other frequently-used names for these two special Nodes are head and tail. There can be other naming schemes as well.
  • start is a pointer that points to the memory address of the first Node in the list. start also has a pointer to the next node in the list (the second node). However, what does stop point to?
  • stop contains a pointer that points to a special value called NULL. Here, NULL indicates that there are no further elements in the list.

Group Activity:

  • Draw the lists of values provided by your instructor as a linked list, including pointers to the start and stop nodes.


Writing Our Own List Class

  • Although C++ has its own linked list class as part of the Standard Template Library (STL), many programmers choose to write their own linked list class rather than using the one provided by the STL.
  • In fact, at a very minimum, every computer science student has had to write their own linked list class at least once.
  • Therefore, we are going to dedicate significant class and homework time to writing our own linked list classes both today and next class.

Review of Linked Lists

  • To get us started thinking about how to write our own linked list class, let's watch the following video:
  • Video: Linked Lists in 10 Minutes


Like any other ADT, our Linked Lists needs to have:

  1. A Way to store data ---> Nodes
  2. Operations we can perform the data (access, manipulate and instantiate) --> Functions


Linked List Data: Defining a Node

  • A node is not a C++ type, so we will need to build our own.
  • What kind of information does a node hold?
    • Some data
    • A pointer to the next node's memory address

A node contains some data and a pointer to the next node's memory address. Image source

  • Therefore, we need to create a node struct containing these two fields.

struct Node
{
    int data;
    Node* next; //pointer to the next node in the linked list
};

  • For the moment, we are going to assume that our linked list holds integer data. We will change this part later.
  • To make our lives easier in the future, let's also define our own constructor

Node(int newData){
    data = newData;
    next = NULL;
}

  • Now, since a Node is an integral part of our linked list, we are going to place the struct definition inside our linked list class.
  • It is going to be one of the linked list's private fields.
class List {
private:
    struct Node {
        int data;
        Node* next;

        Node(int newData){
            data = newData;
            next = NULL;
        }
    };

    //rest of class
};

Question
  • Why do we want to make the Node struct private?


Defining the List and Its Operations

  • Now, we need to determine which operations the list will perform and what fields we need inside our list class for the list to be able to carry out those operations.
  • Let's begin with the fields we need for the list.
  • The best place to begin is by picturing what a list looks like.
  • Remember that the list has pointers to the first and last node (called "start" and "stop") so we can keep track of where they are located in memory.


Representation of a linked list. Notice the node pointers to the first and last nodes. These pointers are named "start" and "stop"

  • Let's also think of the other properties of a list
  • We know that a list has a certain number of values stored in it, aka a length. 
  • Putting all these fundamental parts of a linked list together, we can add some new private fields to the list class.
class List {
private:
    struct Node {
        int data;
        Node* next;

        Node(int newData){
            data = newData;
            next = NULL;
        }

    };
   
    Node* start;
    Node* stop;
    int length;

    //rest of class
};


With a partner discuss:

  • What Kind of Operations Will We Need for the Linked List?
  • Access functions?
  • Manipulations procedures?
  • Constructors?


List Operations:

Constructors:

constructor: constructs a new linked list object.
copy constructor: makes a copy of the list object (Lab 2)
destructor: frees the memory associated with the linked list

Manipulation Procedures:

removeStart: removes the element at the beginning of the list   
removeStop:
removes the element at the end of the list

insertStart: inserts an element at the beginning of the linked list
insertStop: inserts an element at the end of the list

Access Functions:

getStart: returns the first element
getStop:
returns the last element

isEmpty: tests whether the linked list is empty
getLength: returns the current length of the list

Additionally, we will need some accessors and modifiers related to our iterator and a function to print the list:

startIterator: moves the iterator to the start of the list
removeIterator: removes the element currently pointed to by the iterator
getIterator: returns the element currently pointed at by the iterator
insertIterator: inserts an element after the node currently pointed to by the iterator
advanceIterator: moves the iterator up by one node towards the last node
reverseIterator: moves the iterator down by one node towards the first node
offEnd: returns whether the iterator is off the end of the list, i.e. pointing to NULL

displayList: prints the contents of the linked list to the screen <-- Always one of the first functions to write!


Preconditions and Postconditions

  • Preconditions and post-conditions are specifications or requirements for the ADT operations.
  • Preconditions specify under what conditions an operation may be executed.


With a partner discuss:

  • What do you think the precondition will be for the following List function:

int getStart() const;
//Returns the value stored at the start of the list
//Precondition:
  • What do you think the postcondition will be for the following List function:

void insertStart(int data);
//Inserts a new element at the start of the list
//If the list is empty, the new element becomes both start and stop
//Postcondition:

Begin Lab 1


Wrap Up

  • With a partner, answer the questions from today's learning objectives.


Upcoming Assignments