struct Node {
	int data;
	Node* next;
};

struct LinkedList {
  Node* head;
  Node* tail;
};

[10]->[20]->[30]->null

cout << list->head->data << endl; // 10
cout << list->head->next->data << endl; // 20
cout << list->head->next->next->data << endl; // 30
cout << list->head->next->next->next->data << endl; // seg fault!

// LinkedList.h
#ifndef LINKEDLIST_H
#define LINKEDLIST_H

struct Node {
	int data;
	Node* next;
};

struct LinkedList {
	Node* head;
	Node* tail;
};

void printList(LinkedList* list);
void insertToFront(LinkedList* list, int value);
bool exists(LinkedList* list, int value);
int length(LinkedList* list);
void deleteIndex(LinkedList* list, int index);

#endif
--------------
// LinkedList.cpp
#include <iostream>
#include "linkedList.h"
using namespace std;

void printList(LinkedList* list) {
	for (Node* i = list->head; i != NULL; i = i->next) {
		cout << "[" << i->data << "]->";
	}
	cout << "null" << endl;
}

void insertToFront(LinkedList* list, int value) {
	if (list->head == 0) {		// empty list
		Node* item = new Node;
		item->data = value;
		item->next = NULL;
		list->head = item;
		list->tail = item;
	} else { 			// not empty
		Node* item = new Node;
		item->data = value;
		item->next = list->head;
		list->head = item;
	}
}

bool exists(LinkedList* list, int value) {
	for (Node* i = list->head; i != NULL; i = i->next) {
		if (i->data == value)
			return true;
	}
	return false;
}

int length(LinkedList* list) {
	int counter = 0;
	// let's use a while loop instead of a for...
	Node* temp = list->head;
	while (temp != 0) {
		counter++;
		temp = temp->next;
	}
	return counter;
}

void deleteIndex(LinkedList* list, int index) {
	if (index >= length(list) || index < 0) {
		cerr << "Invalid index: " << index << endl;
		return;
	}

	// check if first item
	if (index == 0 && list->head != 0) {
		Node* temp = list->head;
		list->head = list->head->next;
		delete temp;
		return;
	}

	Node* prev = list->head;
	Node* curr = list->head->next;
	for (int i = 1; i < index; i++) {
		prev = prev->next;
		curr = curr->next;
	}

	// remove the current node
	prev->next = curr->next;
	delete curr;

	// re-assign list->tail if curr was the last node.
	if (index == length(list) - 1)
		list->tail = prev;

	return;
}
----------
// main.cpp
#include <iostream>
#include <string>
#include <fstream>
#include "linkedList.h"

using namespace std;

int main() {
	LinkedList* list = new LinkedList;
	list->head = 0;
	list->tail = 0;

	cout << length(list) << endl;

	insertToFront(list, 10);
	cout << length(list) << endl;
	insertToFront(list, 20);
	insertToFront(list, 30);
	printList(list);			// 30->20->10

	cout << exists(list, 15) << endl; 	// 0
	cout << exists(list, 30) << endl; 	// 1
	cout << exists(list, -1) << endl; 	// 0

	cout << length(list) << endl;		// 3

	deleteIndex(list, -1); 			// err
	deleteIndex(list, 5);			// err
	deleteIndex(list, 3);			// err
	deleteIndex(list, 2);			// OK!
	printList(list);			// 30->20->null

	return 0;
}
----------
$ g++ -o main main.cpp LinkedList.cpp

- Tuesday in lecture

Logistics
	- TAs will proctor
	- Bring studentID and a writing utensil
		- Preferable ink or dark led
		- PLEASE WRITE LEGIBLY
	- No electronic devices
	- No book, no notes

Format
	- Similar to midterm 1 (more or less)
	- Possible types of questions
		- Short answers
		- Explain, describe, define, ...
		- Write some code
		- Fill in the blank
		- True / False (if false, explain)
		- Given code, write the output
	- Should take ~ 1 hour (but you have the entire lecture)
	- Covers a broad range of topics, but probably not everything.

Topics
	- Will cover everything up to Tuesday's lecture (8/7) NOT including LinkedLists.
	- Will cover material from lectures, reading, homeworks, and labs.

File IO
	- reading and writing from / to files
	- Appending to / overwriting a file.

C++ build process
	- Breaking code into multiple files (.cpp , .h)
	- Preprocessing vs. Compilation vs. Linking
	- Makefiles
		- General syntax
		- Conceptual understanding
		- Simple g++ compilation rules

TestDriven Development
	- Write a test that does ...
	- Given tests, which ones pass
	- Explain Test Driven Development ...

Arrays
	- Declaration
	- Syntax
	- Reading / writing elements

Number Conversion
	- Any base to base 10 notation
	- Binary to base 10 / Base 10 to binary
	- Hex to binary / binary to Hex

Memory concepts and pointers
	- Pointer syntax
	- Memory sizes of pointers and types
	- Arrays as pointers
	- Dereferencing
	- Pointers to pointers
	- pass by reference vs. pass by value
	- reference variables

Structs
	- Defining / declaring structures
	- pointers to structs
		- "->" operator

Pointer Arithmetic
	- compute the offset of arrays
	- Segmentation faults
	- passing a pointer by value / reference

Dynamic memory management
	- stack vs. heap
	- dynamic allocation / deallocation
		- "new" operator
		- "delete" operator
	- Dangling pointers

Good Luck!