Lecture 2: Lists

Question of the day!

How many programmers does it take to change a light bulb?

None. That's a hardware problem.

Lists

An abstract data type (ADT) is a data type described by pre-defined user operations, such as "insert data at rear," without indicating how each operation is implemented.

Lists are a common ADT for holding data, with operations like appending a data item, removing a data item, searching and printing. Each item in a list ADT is called a node.

Singly-linked Lists

Singly-linked lists is a data structure for implementing a list ADT, where each node has a data and a pointer to the next node. The list structure typically has pointers to the list's first node and last node. The list's first node is called the head, and the last node is the tail.

The head in this case would be the node with value 12 and the tail would be the node with value 37

In order to implement a Linked List, you must define the structure for an individual node.

For a singly-linked list of integers, it may look something like:

struct IntNode{
    int val;
    IntNode* next;
};

In order to implement the Linked List, we store the head of the list, which is a pointer to a IntNode. We also implement methods that insert/remove elements from the list e.g.

class IntLinkedList {
    public:
        void push_front(int val);
        // ...
    private:
        IntNode* head;
    IntNode* tail;
};

Doubly Linked List

In a doubly linked list, each node contains three parts:

Data
Pointer to the next node
Pointer to the previous node

In this case, our new struct may look something like:

struct IntNode{
    int val;
    IntNode* next;
    IntNode* previous;
};

Dummy Nodes

Sometimes, to make edge cases easier to handle, dummy nodes are used at the end of lists. For example:

alt text

In this image the list is of size 1, however there are three nodes. This is because the first and the last nodes are "Dummy Nodes." Dummy Nodes are there to make lists easier to use. For example, without dummy nodes, writting a function typically requires accounting for the special cases such as when the list is empty or size one. Take for example the following code for a push back and pop front for a singly-linked list with only a head pointer.

void IntList :: pushBack(int n){
    if(head == 0){
        head = new Node(n);
        return;
    }
    Node* loop = 0;
    for(loop = head; loop->next != 0; loop = loop->next){}
    loop->next = new Node(n);
}

void IntList :: popFront(){
    if(head == 0){
        return; // list is empty
    }
    else if(head->next == 0){
        delete head;
        head = 0;
    }
    else{
        Node* temp = head;
        head = head->next;
        delete temp;
    }
}

Using Dummy nodes, we can reduce this code to the following:

void IntList :: pushBack(int n){
    Node* loop = 0;
    for(loop = head; loop->next != 0; loop = loop->next){}
    loop->next = new Node(n);
}

void IntList :: popFront(){
    if(head->next == 0){
        return; //list is empty
    }
    else{
        Node* temp = head->next;
        head->next = temp->next;
        delete temp;
    }
}

Notice how in both functions, the if(head == 0) is no longer a case we have to check for (since head will never be 0). This helps simplify the code and handle common edge cases.

Other functions must of course also be changed such as the print function, but the overall complexity of the code decreases. The contents of the dummy node don't matter as they shouldn't ever be seen.

Exercise 1: Fibonacci Exercise

Fn = Fn-1 + Fn-2

F0 = 0, F1 = 1

Write a program that will calculate a specified fibonacci number using the std::list data structure. Think about how to use a list to store values of the formula above.

Input: integer n
Output: nth Fibonacci number

Example:

Which Fibonacci number to calculate: 10
10th Fibonacci number: 55

Exercise 2: Palindrome Exercise

Write a program that will test to see if a specific word is a palindrome using the std::list data structure.

Input: string input
Output: result of the palindrome test

Example:

Enter a word to test for palindrome: tacocats
tacocats is not a palindrome.

Key functions to incorporate: back(), pop_back()

Exercise 3: Animation!

We've written the foundation for a program to create animations in the terminal, all you have to do is connect the dots!

At the moment, the program will push encrypted characters that need to be displayed into a queue, but those characters still need to be put into cout!

Note, since we're giving you a precompiled file, you're going to have to use C9 for this exercise

How to get the code

In your C9 terminal, run the following in the directory where you want the code

git clone https://github.com/scohe001/Animations

You'll notice you now have a main, an Animator class and a couple animation files (don't look at them yet, it'll ruin the surprise!^*).

We've already completely implemented the Animator class for you and compiled it, so all you'll have to do is finish off the main skeleton! The details for doing so are in the comments, so don't just delete them!

Compiling

Since we're using C++11 features and threading, you'll have to compile with the following:

g++ -std=c++11 -pthread -Wall main.cpp animation.o

After you get your main up and running, test it out with all four animations! I'd highly suggest starting with the Eyes animation, as it's the simplest by far of all of them so it'll be easier to debug. Once you get one animation working, they should all work!

Once you have all of the animations working, delete animation.o and use the skeleton animation.cpp we've given you to complete the Animation class! Recompiling the Animation class should look like the following:

g++ -std=c++11 -pthread -c animation.cpp

* Since you're all CS majors I'm sure the lot of you have already looked at them >.>