Section 7. Hash Tables and Linked Lists

Cell* temp = list->next->next;
temp->next = list->next;
list->next->next = list;
list->next->next->next = nullptr;
list = temp;

list->next->next->next = list;
list = list->next->next;
Cell* list2 = list->next->next;
list->next->next = nullptr;

struct Cell {  
    int value;
    Cell* next;
};             

/* Iterative version */
int sumOfElementsIn(Cell* list) {
    int result = 0;
    for (Cell* curr = list; curr != nullptr; curr = curr->next) {
        result += curr->value;
    }
    return result;
}

/* Recursive version. */
int sumOfElementsIn(Cell* list) {
    /* The sum of the elements in an empty list is zero. */
    if (list == nullptr) return 0;

    /* The sum of the elements in a nonempty list is the sum of the elements in
     * the first cell plus the sum of the remaining elements.
     */
    return list->value + sumOfElementsIn(list->next);
}

/* Iterative version */
Cell* lastElementOf(Cell* list) {
    if (list == nullptr) error("Empty lists have no last element.");

    /* Loop forward until the current cell’s next pointer is null. That’s the
     * point where the list ends.
     */
    Cell* result = list;
    while (result->next != nullptr) {
        result = result->next;
    }
    return result;
}

/* Recursive version. */
Cell* lastElementOf(Cell* list) {
    /* Base Case 1: The empty list has no last element. */
    if (list == nullptr) error("Nothing can come from nothing.");

    /* Base Case 2: The only element of a one-element list is the last element. */
    if (list->next == nullptr) return list;

    /* Recursive Case: There’s at least two cells in this list. The last element
     * of the overall list is the last element of the list you get when you drop
     * off the first element.
     */
    return lastElementOf(list->next);
}

Cell* readList() {
    Cell* head = nullptr;
    Cell* tail = nullptr; // There is no last element... at least, not yet. :-)

    while (true) {
        string line = getLine("Next entry: ");
        if (line == "") break;

        /* Get the cell basics set up. It always goes on the end, so its next
         * pointer is always null.
         */
        Cell* cell  = new Cell;
        cell->value = line;
        cell->next  = nullptr;

        /* If the list is empty, this is now both the head and the tail. */
        if (head == nullptr) {
            head = tail = cell;
        }
        /* Otherwise, splice this element in right after the tail. */
        else {
            tail->next = cell;
            tail = cell;
        }
    }
    return head;
}

class Deque {
public:
    Deque();
    ~Deque();

    /* Seems like all containers have the next two functions. :-) */
    bool isEmpty() const;
    int  size() const;

    /* Adds a value to the front or the back of the deque. */
    void pushFront(int value);
    void pushBack(int value);

    /* Looks at, but does not remove, the first/last element of the deque. */
    int peekFront() const;
    int peekBack() const;

    /* Returns and removes the first or last element of the deque. */
    int popFront();
    int popBack();

private:
    struct Cell {
        int value;
        Cell* next;
        Cell* prev;
    };
    Cell* head;
    Cell* tail;
    int   numElems; // Cache for efficiency; makes size() run in time O(1).

    /* Creates a new cell initialized to a given value, but whose next and prev
     * pointers are uninitialized. This cell is intended to be used inside the
     * linked list, and therefore the size field is adjusted appropriately.
     */
    Cell* makeCell(int value);

    /* Destroys the given cell, which is presumed to be in the linked list. */
    void destroy(Cell* toRemove);
};

#include "error.h" // Because bad things happen.

Deque::Deque() {
    /* Set up the empty dummied, doubly-linked list. */
    head = new Cell;
    tail = new Cell;
    head->next = tail;
    tail->prev = head;
    head->prev = tail->next = nullptr;

    numElems = 0;
}

Deque::~Deque() {
    /* Delete all cells in the list, including the head and tail. */
    while (head != nullptr) {
        Cell* next = head->next;
        delete head;
        head = next;
    }
}

/* Because we’ve cached the size, we don’t need to scan through the list when
 * we want to determine how many elements there are.
 */
int Deque::size() const {
    return numElems;
}

/* Good programming exercise: suppose that we didn’t cache the number of elements
 * in the list and that size() had to scan over the entire list in time O(n). How
 * would you implement isEmpty() given that we have a head and tail pointer?
 */
bool Deque::isEmpty() const {
    return size() == 0;
}

/* Our helper function that makes a cell. We could have alternatively defined a
 * constructor on the Cell type (yes, you can do that!), but I chose to do things
 * this way to show off Yet Another Memorable Piece of C++ Syntax. Since the
 * Cell type is nested inside Deque, the return type of this function has to be
 * Deque::Cell*, indicating that Cell is defined inside of Deque.
 */
Deque::Cell* Deque::makeCell(int value) {
    Cell* result = new Cell;
    result->value = value;

    numElems++;
    return result;
}

/* pushFront is essentially insertAfter with the head pointer. */
void Deque::pushFront(int value) {
    Cell* cell = makeCell(value);
    cell->prev = head;
    cell->next = head->next;
    cell->prev->next = cell;
    cell->next->prev = cell;
}

/* pushBack is essentially insertBefore with the tail pointer. */
void Deque::pushBack(int value) {
    Cell* cell = makeCell(value);
    cell->next = tail;
    cell->prev = tail->prev;
    cell->prev->next = cell;
    cell->next->prev = cell;
}

/* To look at the front or back, we have to skip over the head or tail nodes,
 * since they’re dummies and don’t actually have any data in them.
 */
int Deque::peekFront() const {
    if (isEmpty()) error("This is why we can’t have nice things.");
    return head->next->value;
}

int Deque::peekBack() const {
    if (isEmpty()) error("This is why we can’t have nice things.");
    return tail->prev->value;
}

/* The destroy operation is essentially our remove function from earlier.
 * Notice that we do not need to use the full name Deque::Cell here because Cell
 * is an argument to a member function that’s part of the Deque type.
 */
void Deque::destroy(Cell* toRemove) {
    toRemove->next->prev = toRemove->prev;
    toRemove->prev->next = toRemove->next;

    /* At this point it’s spliced out of the list. */
    delete toRemove;
    numElems--;
}

/* popFront and popBack are essentially just wrapped splice-outs. */
int Deque::popFront() {
    int result = peekFront();
    destroy(head->next);
    return result;
}

int Deque::popBack() {
    int result = peekBack();
    destroy(tail->prev);
    return result;
}

/* Given a base, returns its complementary base. */
char complementOf(char base) {
    if (base == 'A') return 'T';
    if (base == 'C') return 'G';
    if (base == 'G') return 'C';
    if (base == 'T') return 'A';
    error("Unknown nucleotide.");
}

void addComplementaryStrand(Nucleotide* dna) {
    while (dna != nullptr) {
        Nucleotide* partner = new Nucleotide;

        /* Set the value. */
        partner->value = complementOf(dna->value);

        /* Wire the across pointers. */
        dna->across = partner;
        partner->across = dna;

        /* As of now, this cell has no next pointer, since we haven't built the
         * next cell yet.
         */
        partner->next = nullptr;

        /* There may be a previous cell, though. */
        if (dna->prev != nullptr) {
            partner->prev = dna->prev->across;
            dna->prev->across->next = partner;
        } else {
            partner->prev = nullptr;
        }

        /* Walk forward to the next cell. */
        dna = dna->next;
    }
}

void removeValuesAbove(Cell*& list, int value) {
    /* Keep track of the previous linked list cell so we can rewire its
     * next pointer if necessary.
     */
    Cell* prev = nullptr;

    /* Walk over the list, removing cells as necessary. */
    Cell* curr = list;
    while (curr != nullptr) {
        /* Do we need to remove this one? */
        if (curr->value > value) {
            /* If we have a previous pointer, wire it around this cell. */
            if (prev != nullptr) {
                prev->next = curr->next;
            }
            /* Otherwise, we are the head of the list. In that case, the
             * list head needs to change, since it's pointing to a cell
             * that will no longer exist.
             */
            else {
                list = list->next;
            }

            /* Remove this cell from the list. */
            Cell* next = curr->next;
            delete curr;
            curr = next;
        }
        /* Otherwise, we don't remove this cell. It's now the previous
         * cell.
         */
        else {
            prev = curr;
            curr = curr->next;
        }
    }
}