Linked list: a linked list consists of a series of nodes that are pointing to each other. Below is how a node may be implemented:

struct: Node {
    int data;
    Node* next;
    Node();
}

OR:

class: Node {
private:
    int data;
    Node* next;

public:
    Node();
    getNext();
    getData();
    setNext(Node* n);
    setData(Node* d);
}

Each node contains two elements: "data" and "next": "data" refers to the value stored inside the node, and "next" is a pointer pointing to the next node in the list. At the end of the list, the last node will point to NULL. The constructor creates a new node.

Linked lists can also include special nodes called "headers" which are the first nodes in the list. They can also include "tails", which is the last element in the list. Naming these nodes can help in solving problems!

In particular, a useful function for nodes is a "getNext" function that returns the value of node the current node is pointing to!

The stack and queue can both be implemented with linked lists (or arrays).

Stack ADT (abstract data type): uses a LIFO approach to storing elements (last in, first out. This means if we push 1, 2, and then 3 to the top of the stack in that order, then pop the stack (this function removes the top element of the stack), then the value 3 will be popped.

How to implement with linked lists: simply have a normal linked list! To do push and pop operations, we must do them from the front of the list so that we can do these operations in O(1) time complexity, like a regular stack. Essentially, the head of the linked list is the top of the stack.

When we add a node, we must make that new node point to the first node of the list.

Visual example: end: H->O->O->O->O->O-|: front

Queue ADT (abstract data type): uses a FIFO approach to storing elements (first in, first out). It also has functions add, remove and empty.

How to implement with linked lists: since we need to delete/add from the front of the queue in O(1) time complexity, we must construct the list such that the front of the list is the front of the queue. Essentially, the head of the linked list is the front of the queue.

Visual example: front: H->O->O->O->O->O-|: end

When we add a node, we must make the last node of the list point to this new node (which we can find in O(1) time using the tail). The new node must then point to null.