Basic Operations on Linked List

DSA, Database System & Operating System — Data Structure, Lists, Linked Lists and Trees, NEC licence examination syllabus (Nepal Engineering Council).

Basic Operations on Linked List

Creating, inserting, and deleting — the three moves you'll implement over and over.

🛠️ Insertion Points

At the beginningNew node points to the old head; new node becomes the head. O(1) — no traversal needed.

At the endTraverse to the last node, then link it to the new node. O(n) for a singly linked list (unless you separately track a "tail" pointer).

In the middleTraverse to the position just before where you want to insert, then relink pointers around the new node.

Deletion follows the same three-position logic — the key detail every implementation must get right is updating the PREVIOUS node's pointer correctly before the deleted node's memory is freed.

💡 Practice writing out (in pseudocode or actual code) insertion and deletion at all three positions — this is one of the most common full-code questions in the subject.

The order of pointer updates

Both insertion and deletion are sequences of pointer assignments where the order matters, and getting it wrong loses the rest of the list. This is the part exam questions test.

INSERT newNode after node p: ✓ correct: newNode.next = p.next // grab the successor FIRST p.next = newNode // then relink p ✗ wrong: p.next = newNode // p's successor is now unreachable newNode.next = p.next // this just points newNode at itself The wrong order loses every node after p, and the final line sets newNode.next to newNode — an infinite loop on traversal.

The rule that prevents it: never overwrite a pointer until whatever it points to has been saved somewhere else. In a singly linked list a lost pointer is unrecoverable, because nothing else refers to that chain.

💡 Deletion needs the same care in reverse: link the predecessor past the doomed node before freeing it. Freeing first leaves you reading memory that has been released — which may appear to work in testing and fail unpredictably later.

Why insertion at the end is the expensive one

📍 Cost by position

BeginningO(1) — the head is already in hand, nothing to search for.

EndO(n) — the last node must be found by walking the whole list, unless a tail pointer is kept.

MiddleO(n) to find the position, then O(1) to relink.

Note that this is the opposite of an array, where appending at the end is cheap and inserting at the front requires shifting everything. Neither structure is faster in general — they are fast at opposite ends, and the right choice depends on where the work happens.

💡 Keeping a tail pointer makes end-insertion O(1) and costs one extra pointer for the whole list, which is why any queue built on a linked list keeps one. It must be updated on every operation that can change the last node, and forgetting that in a deletion is a classic bug.

Syllabus points

Creation of a linked list
Insertion at different positions
Deletion from different positions

Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.