Linked Lists

A linked list stores a sequence as separate nodes connected by links. Unlike an array, the next element need not lie in the next memory position. This trades direct indexing and locality for convenient insertion and removal when the relevant node is already known. A singly linked list stores next links; a doubly linked list also stores previous links. We will implement a doubly linked sequence using integer node IDs instead of raw pointers. This is a practical competition technique for deletion, splicing, and “remove this item, then restore it” operations when IDs are stable.

Prerequisites: Arrays and Vectors, Stacks, and the idea of stable IDs.

Build the idea

1. 1. Separate order from storage. Imagine values 10, 20, 30 stored in nodes 1, 2, 3. The logical order is encoded by links next[1]=2, next[2]=3, not by their numeric IDs. Node 4 can be inserted between 1 and 2 without moving any existing value: redirect a small number of links. In a pointer implementation, nodes are objects containing a value and next/previous pointers. The array-based implementation below stores those fields in vectors indexed by ID. IDs never change, even when the logical order changes.
2. 2. Introduce two sentinels. Node 0 is a head sentinel and node n+1 is a tail sentinel; neither is a real element. Initially, next[i]=i+1 and prev[i]=i-1 along the chain. In an empty list, head points to tail and tail points to head. This removes separate insertion/deletion cases for the first and last real elements. Traversal starts at next[0] and stops at tail. A sentinel simplifies boundaries; it must never be printed or treated as a user element.
3. 3. Delete a known node in constant time. Let L=prev[x] and R=next[x]. Set next[L]=R and prev[R]=L. The two neighbors now point around x. For [1,2,3,4,5], removing node 3 changes next[2] to 4 and prev[4] to 2; every other link stays unchanged. The invariant is that each live forward link has a matching backward link. We mark x inactive rather than freeing storage because the exercise permits restoration. Finding the node by its value first would require a scan; the O(1) claim assumes its ID or iterator is already known.
4. 4. Restore with saved boundary information. Each deletion records (x,L,R) on a stack. Undo restores the newest deletion first by linking L–x–R. This works because later deletions have already been undone, so L and R are adjacent live boundaries again. For example, removing 3 then 2 requires restoring 2 before 3. Restoring arbitrary deletions out of order with the old neighbors is unsafe. The history stack is an explicit part of correctness, not just a convenience. An ignored attempt to delete an already inactive ID creates no history entry.
5. 5. Singly versus doubly linked. A singly linked node uses less link storage, but deleting x requires access to its predecessor to bypass it. Knowing only x is generally insufficient for O(1) deletion; the special “copy the next node” trick changes node identity and cannot delete the last node. A doubly linked list can recover the predecessor directly. In the standard library, std::forward_list is singly linked and uses insert_after/erase_after; std::list is doubly linked and supports insertion/erasure at an iterator. Neither provides constant-time access to the k-th element.
6. 6. Know when an array wins. Node links add memory overhead, and following links tends to have worse cache locality than a contiguous vector. For append-and-scan workloads a vector is usually preferable. Linked lists become attractive for repeated edits at known positions or moving ranges using suitable splice operations. Our fixed node pool cannot create new nodes after input; supporting insertion would allocate a new ID, assign its value, and connect its two neighbors. It also needs a carefully designed undo record. Do not assume a list makes every operation faster merely because deletion changes only links.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<stack>
using namespace std;
struct Removal{
    int x,left,right;
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,q;
    if(!(cin>>n>>q)||n<0||q<0){
        return 0;
    }
    int tail=n+1; // Head 0 and this tail are boundaries, not real values.
    vector<long long>value(n+2);
    vector<int>previous(n+2),next(n+2);
    vector<bool>alive(n+2,true);
    for(int i=1;i<=n;++i){
        cin>>value[i];
    }
    for(int i=0;i<=tail;++i){
        previous[i]=i-1;
        next[i]=i+1;
    }
    stack<Removal>history;
    while(q--){
        char op;
        cin>>op;
        if(op=='D'){
            int x;
            cin>>x; // IDs refer to original positions, not current ranks.
            if(x<1||x>n||!alive[x]){
                continue;
            }
            int l=previous[x],r=next[x];
            history.push({x,l,r});
            // Bypass x in both directions to keep the links consistent.
            next[l]=r;
            previous[r]=l;
            alive[x]=false;
        }
        else if(op=='U'&&!history.empty()){
            // LIFO undo ensures the saved neighbors are adjacent again.
            auto[x,l,r]=history.top();
            history.pop();
            // Restore both boundary links and both links belonging to x.
            next[l]=x;
            previous[x]=l;
            next[x]=r;
            previous[r]=x;
            alive[x]=true;
        }
        else if(op=='P'){
            bool first=true;
            // Follow logical order; deleted IDs may leave gaps in storage.
            for(int x=next[0];x!=tail;x=next[x]){
                if(!first){
                    cout<<' ';
                }
                first=false;
                cout<<value[x];
            }
            if(first){
                cout<<"EMPTY";
            }
            cout<<'\n';
        }
    }
}

Complexity analysis

Initialization takes O(n). Deleting a live known ID and undoing the latest deletion each take O(1); printing takes O(s), where s is the current list length. Finding an element by current position is O(s). The node pool uses O(n) memory. At most n valid removals can remain un-undone, so the history also uses O(n) memory. A pointer-based list has the same structural bounds but additional allocation and link overhead.

Example input and output

Read n q, then n values. Each command is D x (delete original node ID x if live), U (undo the latest valid deletion; do nothing if history is empty), or P (print live values in order, or EMPTY). n and q may be zero.

Input

5 9
10 20 30 40 50
P
D 3
P
D 2
P
U
P
U
P

Output

10 20 30 40 50
10 20 40 50
10 40 50
10 20 40 50
10 20 30 40 50

D 3 removes original node 3, containing 30. D 2 removes 20. Undo restores the most recent deletion first, so 20 returns before 30. Values and original node IDs remain unchanged.

Practical applications

Linked lists suit known-position sequence edits, LRU caches combined with a map, and undoable elimination simulations. Array-based links are useful when nodes have compact IDs. Order statistic trees or implicit treaps are better when edits are addressed by current index and k-th-element queries must be fast.

Check your understanding

What assumption makes deleting a doubly linked list node O(1)?

Put it into practice

Add a command that prints the live sequence in reverse.