Linear Data Structures

Node Implementation

8 min code

What to say

Every structure today is made of nodes: a value and a pointer to the next node. The last node points to NULL.
Write the class, create a few nodes with new, link them by hand, and walk the chain with ->next->next.
The template version is the same node for any type — Node<string>, Node<int>.

Basic node structure

#include <iostream>
using namespace std;

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

    Node(int data) {
        this->data = data;
        this->next = NULL;
    }
};

A value and one pointer. A new node points nowhere yet, so next starts as NULL.

n1 → [10|•] → [20|•] → [30|✕]

Template node for generic types

template<typename T>
class Node {
    public:
    T data;
    Node<T> *next;

    Node(T data) {
        this->data = data;
        this->next = NULL;
    }
};

int main() {
    Node<string> *n1 = new Node<string>("hello");
    Node<string> *n2 = new Node<string>("world");
    Node<string> *n3 = new Node<string>("test");
    n1->next = n2;
    n2->next = n3;
    cout << n1->next->next->data;
    return 0;
}

output

test

n1->next->next is the third node, so the program prints its value.

Another version · five nodes linked by hand

Five nodes, four links, and one long walk: node1->next->next->next is the fourth node.

nodes — the full program29 lines

#include <iostream>

using namespace std;

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

    Node(int data){
        this->data = data;
        next = NULL;
    }
};

int main() {
    Node *node1 = new Node(10);
    Node *node2 = new Node(20);
    Node *node3 = new Node(30);
    Node *node4 = new Node(40);
    Node *node5 = new Node(50);
    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node5;
    // cout << node1 << " " << node1->data << " " << node1->next << " " << node2;
    cout << node1->next->next->next->data;
    return 0;
}

output

Stack — LIFO (Last In, First Out)

12 min code

What to say

A stack of plates: you only add to the top and take from the top. Last in, first out.
Every operation is O(1) — push, pop, top, empty, size.
First the STL stack, then the same thing on nodes: the top of the stack is the head of the chain, push puts a new node in front of it.

Core operations

push(item) — add an item to the top — O(1)
pop() — remove the top item — O(1)
top() / peek() — view the top item without removing it — O(1)
empty() — check if the stack is empty — O(1)
size() — get the number of elements — O(1)

C++ implementation using STL

// C++ built-in stack
#include <iostream>
#include <stack>
using namespace std;

int main() {
   stack<int> st;
   st.push(10);
   st.push(20);
   st.push(15);
   st.push(1);

   cout << st.top() << endl; // 1
   st.pop();
   st.pop();
   cout << st.top() << endl; // 20
   cout << st.size() << endl;
   cout << st.empty();
   return 0;
}

output

After pushing 10, 20, 15, 1 the top is 1; two pops remove 1 and 15, so the top is 20 and two elements are left. empty() prints as 0 — false.

Custom stack implementation

class Stack {
    public:
    Node *top;
    int sz;

    Stack() {
        top = NULL;
        sz = 0;
    }

    void push(int data) {
        Node *node = new Node(data);
        node->next = top;
        top = node;
        sz++;
    }

    void pop() {
        if (top != NULL) {
            top = top->next;
            sz--;
        }
    }

    int size() {
        return this->sz;
    }

    bool empty() {
        return (sz == 0);
    }
};

push: the new node points at the old top and becomes the top. pop: the top moves one node down.

Another version · stack with a test

The same stack with a main: push 10, 20, 30, pop once — two elements left, 20 on top.

stack — the full program59 lines

#include <iostream>

using namespace std;

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

    Node(int data){
        this->data = data;
        next = NULL;
    }
};

class Stack {
    public:
    Node *top;
    int sz;

    Stack() {
        top = NULL;
        sz = 0;
    }

    void push(int data) {
        Node *new_node = new Node(data);
        new_node->next = top;
        top = new_node;
        sz++;
    }

    void pop() {
        if (top == NULL)
            return;
        Node *old = top;
        top = top->next;
        delete old;   // added: free the removed node
        sz--;
    }

    bool empty() {
        return sz == 0;
    }

    int size() {
        return sz;
    }
};

int main() {
    Stack *st = new Stack();
    st->push(10);
    st->push(20);
    st->push(30);
    st->pop();
    cout << st->size() << " " << st->top->data;
    return 0;
}

output

2 20

Stack Problems

12 min code

What to say

Start with only round brackets and no stack: a counter goes up on ( and down on ). It must never go negative and must end at zero.
Then ask what breaks with three kinds of brackets. A counter cannot tell ( from [ — we need to remember which bracket was opened last. That is exactly a stack.
The stack version: push every opening bracket; on a closing one, the top must be its pair — pop it. At the end the stack must be empty.

Simple problem · basic parentheses balance

Check if only () brackets are properly balanced. Try solving without a stack first:

#include <iostream>
using namespace std;

// Simple counter approach - works only for () brackets
bool simple_balance(string s) {
    int counter = 0;
    
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(') {
            counter++;
        } else if (s[i] == ')') {
            counter--;
            // If counter goes negative, we have ')' before '('
            if (counter < 0) {
                return false;
            }
        }
    }
    
    // Should end with counter = 0
    return (counter == 0);
}

int main() {
    string s;
    cin >> s;
    if (simple_balance(s))
        cout << "YES";
    else
        cout << "NO";
    return 0;
}

Examples:

"()" → True
"(())" → True
"(((" → False
")))" → False
"()(" → False

Why this approach fails for multiple bracket types

A counter cannot distinguish between different bracket types
Count every opening bracket as +1 and every closing one as −1, and "(]" or "([)]" come out balanced — both are accepted, which is wrong
We need to remember which opening bracket we saw

Classic problem · balanced brackets

Check if brackets are properly balanced: (), [], {}.

#include <iostream>
#include <stack>
using namespace std;

bool is_ok(string s) {
    stack<char> st;

    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(' || s[i] == '{' || s[i] == '[')
            st.push(s[i]);
        else {
            if (st.empty())
                return false;
            if (s[i] == '}' && st.top() != '{')
                return false;
            if (s[i] == ']' && st.top() != '[')
                return false;
            if (s[i] == ')' && st.top() != '(')
                return false;
            st.pop();                
        }
    }
    return (st.empty());
}

int main() {
    string s;
    cin >> s;
    if (is_ok(s))
        cout << "YES";
    else
        cout << "NO";
    return 0;
}

Examples:

"()" → True
"([{}])" → True
"([)]" → False
"(((" → False

Applications: function call management, expression evaluation, undo operations, browser history.

Queue — FIFO (First In, First Out)

8 min code

What to say

A line at a store: the first person in line is served first. First in, first out.
Elements come in at the rear and leave from the front; all operations are O(1).
The queue is what breadth-first search runs on — the two problems after the deque are both BFS.

Core operations

push() / enqueue(item) — add an item to the rear — O(1)
pop() / dequeue() — remove the front item — O(1)
front() — view the front item without removing it — O(1)
empty() — check if the queue is empty — O(1)
size() — get the number of elements — O(1)

C++ implementation using STL

#include <queue>
#include <iostream>
using namespace std;

void demo_stl_queue() {
    queue<int> q;
    
    // Add elements
    q.push(10);
    q.push(20);
    q.push(30);
    
    cout << "Queue size: " << q.size() << endl;
    cout << "Front element: " << q.front() << endl;
    
    // Remove elements
    while (!q.empty()) {
        cout << "Removing: " << q.front() << endl;
        q.pop();
    }
}

Called from main, it prints:

output

Queue size: 3
Front element: 10
Removing: 10
Removing: 20
Removing: 30

Applications

Task scheduling in operating systems
Breadth-First Search (BFS) in graphs
Print job management
Buffer for data streams

Another version · queue on nodes

The same queue built from nodes: front is where elements leave, end is where they arrive. When the last element leaves, both become NULL.

class Queue {
    public:
    Node *front;
    Node *end;
    Queue() {
        front = NULL;
        end = NULL;
    }
    void push(int val) {
        Node* newNode = new Node(val);
        if (end == NULL) {
            front = end = newNode;
            return;
        }
        end->next = newNode;
        end = newNode;
    }
    void pop() {
        if (front == NULL) 
            return;
        Node* temp = front;
        front = front->next;
        if (front == NULL) 
            end = NULL;
        delete temp;
    }
    int peek() {
        if (front == NULL) 
            return -1; // or throw an exception
        return front->data;
    }
    int empty() {   
        return front == NULL;
    }
    int size() {
        int count = 0;
        Node* current = front;
        while (current != NULL) {
            count++;
            current = current->next;
        }
        return count;
    }

};

Deque — Double-Ended Queue

5 min code

What to say

A combination of a stack and a queue: add and remove at both ends, all in O(1).
Trace the four lines on the board: push_front puts the element before everything else.

Core operations

push_back(item) — add an item to the back — O(1)
push_front(item) — add an item to the front — O(1)
pop_back() — remove the back item — O(1)
pop_front() — remove the front item — O(1)

deque<int> q;
q.push_back(10); 
q.push_back(20);
q.push_front(30);
q.push_front(40);

Front to back, the deque now holds

40 30 10 20

Problem: Minimum Operations to Transform Number

12 min code BFS

What to say

Given a and b, the fewest operations +1, ×2, ÷2, −1 that turn a into b.
Every number is a state, every operation is a step. BFS visits states in order of distance, so the first time it reaches b the distance is minimal.
used[x] stores the number we came from — that is how the path is printed backwards from b.

Problem statement

Given two positive integers a and b, find the minimum number of operations needed to transform a into b:

Add 1: x → x + 1
Multiply by 2: x → x * 2
Divide by 2: x → x / 2 (integer division)
Subtract 1: x → x − 1 (if the result ≥ 0)

Example: a = 2, b = 12 → 3 operations, path 2 → 3 → 6 → 12.

Algorithm · BFS guarantees the minimum

#include <iostream>
#include <queue>
using namespace std;

queue<pair<int, int> > q;
int used[1000]; 

int f(int a, int b) {
    q.push(make_pair(a, 0));
    used[a] = a;

    while (!q.empty()) {
        int x = q.front().first;
        int d = q.front().second;

        if (x == b) {
            return d;
        }

        if (x + 1 < 1000 && used[x + 1] == 0) {   // stay inside used[]
            q.push(make_pair(x + 1, d + 1));
            used[x + 1] = x;
        }

        if (x * 2 < 1000 && used[x * 2] == 0) {   // stay inside used[]
            q.push(make_pair(x * 2, d + 1));
            used[x * 2] = x;
        }

        if (used[x / 2] == 0) {
            q.push(make_pair(x / 2, d + 1));
            used[x / 2] = x;
        }

        if (x - 1 >= 0 && used[x - 1] == 0) {
            q.push(make_pair(x - 1, d + 1));
            used[x - 1] = x;
        }
        q.pop();
    }
    return 0;
}

int main() {
    int a, b;
    cin >> a >> b;
    cout << f(a, b) << endl;

    vector<int> result;
    result.push_back(b);
    int t = b;
    while (used[t] != t) {
        t = used[t];
        result.push_back(t);
    }

    for (int i = result.size() - 1; i >= 0; i--)
        cout << result[i] << " ";

    return 0;
}

input

2 12

output

3
2 3 6 12

The first line is the number of operations, the second the path. The two range checks keep x + 1 and x * 2 inside used[1000].

Problem: Knight's Shortest Path on Chessboard

10 min code BFS

What to say

Same BFS, different states: a state is a square, a step is one of the eight knight moves.
a[x][y] is both "visited" and the distance (+1, because the start is marked 1); c[x][y] is the square we came from.

Problem statement

On a standard 8×8 chessboard, find the minimum number of moves for a knight to travel from (x1, y1) to (x2, y2).

BFS over the board

#include <iostream>
#include <queue>
using namespace std;

int a[10][10];
pair<int, int> c[10][10];
queue<pair<int, int> > q;

int dx[8] = {2,  2, -2, -2,  1, 1, -1, -1};
int dy[8] = {1, -1,  1, -1, -2, 2, -2,  2};

bool check(int x, int y) {
    return (x >= 1 && x <= 8 && y >= 1 && y <= 8 && a[x][y] == 0);
}

int main() {
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    a[x1][y1] = 1;
    q.push(make_pair(x1, y1));
    c[x1][y1] = make_pair(x1, y1);

    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;

        for (int i = 0; i < 8; i++) {
            if (check(x + dx[i], y + dy[i])) {
                q.push(make_pair(x + dx[i], y + dy[i]));
                a[x + dx[i]][y + dy[i]] = a[x][y] + 1;
                c[x + dx[i]][y + dy[i]] = make_pair(x, y);
            }
        }
        q.pop();
    }

    cout << a[x2][y2] - 1 << endl;

    vector<pair<int, int> > result;
    result.push_back(make_pair(x2, y2));
    int x = x2;
    int y = y2;
    while (c[x][y] != make_pair(x, y)) {
        int x_temp = c[x][y].first;
        int y_temp = c[x][y].second; 
        result.push_back(make_pair(x_temp, y_temp));
        x = x_temp;
        y = y_temp;
    }

    for (int i = result.size() - 1; i >= 0; i--)
        cout << result[i].first << " " << result[i].second << endl;
    return 0;
}

input

1 1 8 8

output

Six moves from one corner to the opposite one, then the squares of one shortest path.

Linked List

25 min code demos

What to say

A doubly linked list: every node has next and prev, the list keeps front and tail.
Write it function by function: push_back and push_front, pop_back and pop_front, delete a node you hold, print, find, insert after a node.
Each function has an empty-list case and a one-element case — say them out loud every time.
Deleting a node you hold is O(1): its neighbours are one pointer away in both directions.

1 · The node

class Node {
    public:
    int data;
    Node *next, *prev;

    Node(int data) {
        this->data = data;
        this->next = NULL;
        this->prev = NULL;
    }
};

2 · The list and push

class LinkedList {
    public:
    Node *tail, *front;
    
    LinkedList() {
        tail = NULL;
        front = NULL;
    }

    ...
};

void push_back(int data) {
    Node *node = new Node(data);
    if (tail == NULL) {
        tail = node;
        front = node;
    } else {
        node->prev = tail;
        tail->next = node;
        tail = node;
    }
}

void push_front(int data) {
    Node *node = new Node(data);
    if (front == NULL) {
        tail = node;
        front = node;
    } else {
        front->prev = node;
        node->next = front;
        front = node;
    }
}

If the list is empty, the new node is both front and tail. Otherwise link it to the end it is added to.

3 · pop_back and pop_front

void pop_back() {
    if (tail != NULL) {
        tail = tail->prev;
        if (tail != NULL)
            tail->next = NULL;
        else 
            front = NULL;
    }
}

void pop_front() {
    if (front != NULL) {
        front = front->next;
        if (front != NULL)
            front->prev = NULL;
        else
            tail = NULL;
    }
}

When the last element leaves, both ends become NULL.

4 · Delete a node

void del_node(Node *node) {
    if (node == tail)
        pop_back();
    else if (node == front) 
        pop_front();
    else {
        Node *a = node->prev;
        Node *b = node->next;
        a->next = b;
        b->prev = a;
    }
}

Tail and front are special; any other node is unlinked by joining its two neighbours.

5 · print and find_node

void print() {
    Node *node = front;
    while (node != NULL) {
        cout << node->data << " ";
        node = node->next;
    }
    cout << endl;
}

Node* find_node(int data) {
    Node *node = front;
    while (node != NULL) {
        if (node->data == data)
            return node;
        node = node->next; 
    }
    return NULL;
}

6 · Insert after a node

void insert_node(Node *node1, int data) {
    Node *node = new Node(data);
    if (node1 == tail) 
        push_back(data);
    else {
        Node *node2 = node1->next;
        node1->next = node;
        node->prev = node1;
        node->next = node2;
        node2->prev = node;
    }
}

7 · main — and what it prints

int main() {
    LinkedList *ll = new LinkedList();
    ll->push_back(5);
    ll->push_back(6);
    ll->push_back(7);
    ll->push_back(8);
    ll->push_back(9);
    ll->push_back(10);
    ll->push_front(11);
    ll->push_front(12);
    ll->push_front(13);
    ll->push_front(14);
    ll->push_front(15);
    ll->print();
    cout << ll->front->data << " " << ll->tail->data << endl;
    ll->pop_back(); 
    ll->pop_back();
    ll->pop_front(); 
    ll->pop_front();
    ll->print();
    cout << ll->front->data << " " << ll->tail->data << endl;

    Node *node = ll->find_node(11);
    if (node != NULL) {
        ll->del_node(node);
    }

    ll->print();

    node = ll->find_node(6);
    ll->insert_node(node, 100);
    ll->print();
    return 0;
}

output

15 14 13 12 11 5 6 7 8 9 10
15 10
13 12 11 5 6 7 8
13 8
13 12 5 6 7 8
13 12 5 6 100 7 8

The whole program

Everything above in one file — open it and press ▶ edit & run.

doubly linked list — the full program148 lines

#include <iostream>
using namespace std;

class Node {
    public:
    int data;
    Node *next, *prev;

    Node(int data) {
        this->data = data;
        this->next = NULL;
        this->prev = NULL;
    }
};

class LinkedList {
    public:
    Node *tail, *front;
    
    LinkedList() {
        tail = NULL;
        front = NULL;
    }

    void push_back(int data) {
        Node *node = new Node(data);
        if (tail == NULL) {
            tail = node;
            front = node;
        } else {
            node->prev = tail;
            tail->next = node;
            tail = node;
        }
    }

    void push_front(int data) {
        Node *node = new Node(data);
        if (front == NULL) {
            tail = node;
            front = node;
        } else {
            front->prev = node;
            node->next = front;
            front = node;
        }
    }

    void pop_back() {
        if (tail != NULL) {
            tail = tail->prev;
            if (tail != NULL)
                tail->next = NULL;
            else 
                front = NULL;
        }
    }

    void pop_front() {
        if (front != NULL) {
            front = front->next;
            if (front != NULL)
                front->prev = NULL;
            else
                tail = NULL;
        }
    }

    void del_node(Node *node) {
        if (node == tail)
            pop_back();
        else if (node == front) 
            pop_front();
        else {
            Node *a = node->prev;
            Node *b = node->next;
            a->next = b;
            b->prev = a;
        }
    }

    void print() {
        Node *node = front;
        while (node != NULL) {
            cout << node->data << " ";
            node = node->next;
        }
        cout << endl;
    }

    Node* find_node(int data) {
        Node *node = front;
        while (node != NULL) {
            if (node->data == data)
                return node;
            node = node->next; 
        }
        return NULL;
    }

    void insert_node(Node *node1, int data) {
        Node *node = new Node(data);
        if (node1 == tail) 
            push_back(data);
        else {
            Node *node2 = node1->next;
            node1->next = node;
            node->prev = node1;
            node->next = node2;
            node2->prev = node;
        }
    }
};

int main() {
    LinkedList *ll = new LinkedList();
    ll->push_back(5);
    ll->push_back(6);
    ll->push_back(7);
    ll->push_back(8);
    ll->push_back(9);
    ll->push_back(10);
    ll->push_front(11);
    ll->push_front(12);
    ll->push_front(13);
    ll->push_front(14);
    ll->push_front(15);
    ll->print();
    cout << ll->front->data << " " << ll->tail->data << endl;
    ll->pop_back(); 
    ll->pop_back();
    ll->pop_front(); 
    ll->pop_front();
    ll->print();
    cout << ll->front->data << " " << ll->tail->data << endl;

    Node *node = ll->find_node(11);
    if (node != NULL) {
        ll->del_node(node);
    }

    ll->print();

    node = ll->find_node(6);
    ll->insert_node(node, 100);
    ll->print();
    return 0;
}

Demo · list playground

Empty list. head = nullptr.

size

pointer writes

nodes walked

Watch the two counters: push_front never walks, insert in the middle always does. That gap is the whole lecture.

Demo · reverse, one step at a time

length

null

cur

—

nxt

—

Press Step. Green is the part already reversed.

Another version · list, stack, queue and a singly linked list

One file with four classes. The doubly linked list here has no pop_front, so deleting the first node is written out in place:

class LinkedList {
    public:
    Node *tail;
    Node *front;
    int data;

    LinkedList() {
        tail = front = NULL;
    }

    void push_front(int data) {
        Node *node = new Node(data);
        if (front == NULL) {
            front = tail = node;
        } else {
            node->next = front;
            front->prev = node;
            front = node;
        }
    }

    void push_back(int data) {
        Node *node = new Node(data);
        if (front == NULL) {
            front = tail = node;
        } else {
            tail->next = node;
            node->prev = tail;
            tail = node;
        }
    }
    
    void pop_back() {
        if (tail != NULL) {
            Node *temp = tail;
            tail = tail->prev;
            if (tail != NULL)
                tail->next = NULL;
            else
                front = NULL;   // added: the list is empty now
            delete temp;            
        }
    }

    void del_node(Node *node) {
        if (node == tail)
            this->pop_back();
        else if (node == front) {
            front = front->next;   // added: this case did nothing
            front->prev = NULL;
            delete node;
        } else {
            Node *a = node->prev;
            Node *b = node->next;
            a->next = b;
            b->prev = a;
            delete node;           // added: free the removed node
        }
    }
};

four classes — the full program231 lines

#include <iostream>

using namespace std;

class Node {
    public:
    int data;
    Node *next;
    Node *prev;
    Node(int val) {
        this->data = val;
        this->next = nullptr;
        this->prev = nullptr;
    }
};

class LinkedList {
    public:
    Node *tail;
    Node *front;
    int data;

    LinkedList() {
        tail = front = NULL;
    }

    void push_front(int data) {
        Node *node = new Node(data);
        if (front == NULL) {
            front = tail = node;
        } else {
            node->next = front;
            front->prev = node;
            front = node;
        }
    }

    void push_back(int data) {
        Node *node = new Node(data);
        if (front == NULL) {
            front = tail = node;
        } else {
            tail->next = node;
            node->prev = tail;
            tail = node;
        }
    }
    
    void pop_back() {
        if (tail != NULL) {
            Node *temp = tail;
            tail = tail->prev;
            if (tail != NULL)
                tail->next = NULL;
            else
                front = NULL;   // added: the list is empty now
            delete temp;            
        }
    }

    void del_node(Node *node) {
        if (node == tail)
            this->pop_back();
        else if (node == front) {
            front = front->next;   // added: this case did nothing
            front->prev = NULL;
            delete node;
        } else {
            Node *a = node->prev;
            Node *b = node->next;
            a->next = b;
            b->prev = a;
            delete node;           // added: free the removed node
        }
    }
};

class Stack {
    public:
    Node* top;
    int sz;
    Stack() {
        top = NULL;
        sz = 0;
    }
    void push(int val) {
        Node *newNode = new Node(val);
        newNode->next = top;
        top = newNode;
        this->sz++;
    }

    int peek() {
        if (top == NULL) 
            return -1; // or throw an exception
        return top->data;
    }
    int size() {
        return sz;
    }
    int empty() {
        return sz == 0;
    }
};

class Queue {
    public:
    Node *front;
    Node *end;
    Queue() {
        front = NULL;
        end = NULL;
    }
    void push(int val) {
        Node* newNode = new Node(val);
        if (end == NULL) {
            front = end = newNode;
            return;
        }
        end->next = newNode;
        end = newNode;
    }
    void pop() {
        if (front == NULL) 
            return;
        Node* temp = front;
        front = front->next;
        if (front == NULL) 
            end = NULL;
        delete temp;
    }
    int peek() {
        if (front == NULL) 
            return -1; // or throw an exception
        return front->data;
    }
    int empty() {   
        return front == NULL;
    }
    int size() {
        int count = 0;
        Node* current = front;
        while (current != NULL) {
            count++;
            current = current->next;
        }
        return count;
    }

};

class SinglyLinkedList {   // renamed: the file already has a LinkedList above
    public:
    Node* head;
    Node* tail;
    int sz;
    SinglyLinkedList() {
        head = NULL;
        tail = NULL;
        sz = 0;
    }

    void insert_at_head(int val) {
        Node* newNode = new Node(val);
        if (head == NULL) {
            head = tail = newNode;
        } else {
            newNode->next = head;
            head = newNode;
        }
        sz++;
    }

    void insert_at_tail(int val) {
        Node* newNode = new Node(val);
        if (tail == NULL) {
            head = tail = newNode;
        } else {
            tail->next = newNode;
            tail = newNode;
        }
        sz++;
    }

    void delete_from_head() {
        if (head == NULL) 
            return;
        Node* temp = head;
        head = head->next;
        if (head == NULL) 
            tail = NULL;
        delete temp;
        sz--;
    }

    void delete_from_tail() {
        if (tail == NULL) 
            return;
        if (head == tail) {
            delete head;
            head = tail = NULL;
            sz--;
            return;
        }
        Node* current = head;
        while (current->next != tail) {
            current = current->next;
        }
        delete tail;
        tail = current;
        tail->next = NULL;
        sz--;
    }

    int size() {
        return sz;
    }

    bool empty() {
        return sz == 0;
    }
};
int main() {
    Node *node1 = new Node(10);
    Node *node2 = new Node(20);
    Node *node3 = new Node(30);
    node1->next = node2;
    node2->next = node3;
    cout << node1->next->next->data;
    return 0;
}

output

Data Structures Summary

4 min board

Side by side

Data Structure	Access	Insert	Delete	Search	Space
Stack	O(1) top only	O(1)	O(1)	O(n)	O(n)
Queue	O(1) front/rear	O(1)	O(1)	O(n)	O(n)
Deque	O(1) both ends	O(1)	O(1)	O(n)	O(n)
Linked List	O(n)	O(1) with pointer	O(1) with pointer	O(n)	O(n)

Key Takeaways

3 min

Six things to remember

Choose the right data structure based on your access patterns
Stack: when you need LIFO behaviour — undo operations, function calls
Queue: when you need FIFO behaviour — BFS, task scheduling
Deque: when you need both stack and queue operations
Linked List: when frequent insertions and deletions and a dynamic size matter
Understanding pointers and memory management is crucial for implementing these structures

Lab 2 — the problems

10 min ADS-Lab-02

Problem to topic

One-time guests

Queue in disguise — the intended solve is a single pass with a counter, no list needed

Kuanyshbek

Delete every k-th node while walking the chain

Databasefixed

Delete a node equal to its immediate predecessor

Reverse the Linked Listnew

Reverse a linked list — three pointers, O(1) memory; the reverse demo

Delete the Middle Nodenew

Delete the middle node — slow and fast runners

Merge Two Sorted Listsnew

Merge two sorted lists by relinking, not copying

Jonathan the Poet

Walk the chain and collect; an array passes just as well

Ragnarok

Kadane with n ≤ 100 — nothing list-specific

Doubly linked listkey

Doubly linked list by hand — the one problem a vector cannot carry

Zoro and Seven Sword Style.fixed

Full list interface by index; watch the empty-list print case

At the defence you will be asked to show the pointers. Every problem except I also passes with a plain array or vector — the judge accepts it, the defence does not. Limits: 1 s and 256 MB, except I at 2 s and J at 1.5 s.

Known rough edges: in B the jury solution is O(N²) although the editorial promises one pass, and its size field goes stale on a no-op delete — harmless for the output, but do not read that code aloud as exemplary.