Lecture 6 - Linked Lists (vs Arrays)

Singly linked, Doubly linked, or Circularly Linked (last node points to first node)

Deleting Node in Singly-Linked List: O(n) vs Doubly-Linked: O(1)

Arrays:

• Start_ptr: pointer pointing to start of array

• End_ptr: pointer to one past the end of the array (cannot access this), ++'ing start ptr will eventually reach this

• Size: stores size of array

Linked Lists

• Size: matches no. of elements
• head ptr (begin? front?)
• tail ptr (NOT end, maybe back)

Merging Unsorted Linked Lists- easy

Merging Sorted Lists - O(n) time possibly, Lab 5 Problem using PQs?

Reversing Linked Lists:

1. Copying-ish, using another "result" linked-list: Push each node in the linked list to the new list O(n) time, O(n) memory
2. In-Place: Curr node has its "next" point to nullptr at end, curr node advances, curr node has next point to prev node, etc.
   1. 3 local variables: Prev, Curr, Next

Reversing Doubly-Linked Lists: O(1) time, O(1) memory

• You can try setting a reverse flag and hack the ++ to be -- (scary)

• Declare reverse_iterator, built in
  
  List::reverse_iterator rit; rit = l.rbegin(); rit < l.rend(); ++rit
  

Traversing Linked Lists and Arrays (with Nodes or Pointers)

Traversing Linked Lists
void LinkedList::print() {
    Node *current = headPtr;
    while(current!=nullptr) {  // nullptr is the end
        cout << current->item << '\n';
        current = current->next;
    } // while
} // print

Traversing Arrays
void Array::print() {
    double *current = data;  // data is arrays current points to start right now, and then advances with ++
    while(current != data + size) {  // data + size is the end
        cout << *current << '\n';
        ++current;
    }
}

Generic Programming (using InputIterators and Templates here)

With a genPrint fcn that takes in 2 input interators, you can print LinkedLists and Arrays the same way
template<class InputIterator>
void genPrint(InputIterator itBegin, InputIterator itEnd) {
    // ...
}

void LinkedList::print() {
    genPrint(this->begin(), this->end());
} 
void Array::print() {
    genPrint(this->begin(), this->end());
}

Iterators for Linked Lists, need to declare itr++, ++itr operators (post-fix and pre-fix)

Some form of:
ListIter &operator++() {
    ptr = ptr->next;
    return *this;
}