L17 - Linked Lists and Stacks

Can I finally add DSA to my resume 🥺

the problem with standard arrays

A standard array is easy to create initially, however, they are not flexible. Namely:

An array created by int arr[x] will always have a size of x
If we wish to add more than x items to the array, we must:
1. Allocate a new larger block of memory
2. Copy all the data from the old array to the new one
3. Delete the old array
And this is very inefficient as a data structure

linked lists

Recall: linked lists from APS105; they are generally the same in C++. Linked lists solve the inefficiencies of standard arrays by using nodes.

Nodes contain:

the data itself (e.g. an int)
a pointer to the next node in the chain

You can obviously have a pointer to the previous chain as well (or only a pointer to the previous chain); this was not covered in Salma's L17 notes. For more info, see: APS105 notes.

The Node class:

// in Node.h file
class Node {
	private:
		int data;
		Node *next // pointer to next node in linked list
	public:
		Node(int d, Node* n) {
			data = d;
			next = n;
		}
		
		~Node() {
			delete next; // recursively delete the *next* node
		}
		// "Getter" and "Setter" functions to access private data
		int getData() { return data; }
		Node* getNext() { return next; }
		void setData(int d) { data = d; }
		void setNext(Node* n) { next = n; }
}

In another class, we will store the head of the linked list, along with several operations specific to its "tyoe" (not data type). One of these types is called a Stack.

data structure: stacks

A Stack is a LIFO (Last-In, First-Out) data structure. It consists of two functions in the class definition:

push(), which inserts a new node at the head of the linked list
pop(), which removes the node that was most recently added, which is also the head
Both operations only occur at the head of the linked list, so that's the only pointer we need to track.

Stack analogy

Think of it like a stack of plates, where you can only add OR remove plates from the top, not from the bottom.

stack implementation

Below is an implementation of a stack data structure. Note that we are referring to the Node class, as defined above.

class Stack {
	private:
		Node *head; // head is a pointer to a Node object
	public:
		// Constructor called when new stack is created; no items in list
		Stack() { head = nullptr; }
		
		// Destructor: Just delete the head node, because every other node
		// will delete recursively!
		~Stack() {
			delete head;
		}
		
		void push(int d) { // add node to top
			// 1. create a new node at the front (head)
			// 2. set its 'next' pointer to be the current head object
			Node *p = new Node(d, head);
			// 3. update 'head' to point to our new node
			// we can do this bc head is fed into Node as a copy
			head = p;
		}
		
		int pop() { // remove node from top
			// 1. check for an empty stack
			if (head == nullptr) {
				return -1;
				// return an error if you try to remove from an empty stack
			}
			// 2. create a temp ptr to node we wish to remove
			Node *p = head;
			// 3. retrieve data from node to return it later
			int d = p->getData();
			// 4. reassign 'head' ptr to ptr to next node in list
			head = p->getNext();
			// 5. CRITICAL STEP: isolate node to be deleted
			// very important to ensure that 'delete p' won't trigger
			// recursive destructor, thereby deleting the entire linked list
			p->setNext(NULL);
			// 6. delete node
			delete p;
			// 7. return the data of the node we deleted
			return d;
		}
}

Notes:

push() works for both empty stacks and stacks that have nodes
- if stack is empty, then the new node it allocates will point to NULL, thus signifying the end of the linked list
- if the stack has nodes, then it will feed in the previous head pointer to be the next node pointer.
We must ensure that pop() doesn't delete the entire linked list by reassigning its next pointer to point to NULL instead of the new head of the linked list.

example main function using stack implementation

int main(void) {
	Stack s;
	s.push(1);
	s.push(0);
	// so first node is 0, then it's 1, then it's NULL
	
	cout << s.pop() << s.pop() << endl;
	// prints "01" because 0 was last in
	return 0;
}