Linked Lists: Nodes and Links
A linked list stores data in nodes connected by references rather than contiguous array positions. Each node contains data and links that determine the list's order.
Summary
A linked list stores data in nodes connected by references rather than contiguous array positions. Each node contains data and links that determine the list's order. The head references the first node; an empty list has a null head. An optional tail references the last node. In a null-terminated list, the last node's next reference is null.
| Structure | Node references | Traversal |
|---|---|---|
| Singly linked list | Next | Forward |
| Doubly linked list | Next and previous | Forward and backward |
To insert after a known node p, first set new.next = p.next, then set p.next = new. This preserves access to the original successor. To delete p's successor when it exists, set p.next = p.next.next. With manual memory management, the removed node must also be deallocated without leaving dangling references.
Local insertion takes time once the location is known. Singly linked deletion takes time when the predecessor is available, but finding it can take time. Worst-case indexed access also takes time because traversal follows links sequentially. Linked lists avoid shifting later elements during local updates, but sequential access and reference overhead can make arrays preferable for frequent indexed reads.
🧠 Key Concepts
- Node structure
- Head and tail
- Null termination
- Singly linked lists
- Doubly linked lists
- Sequential traversal
- Local insertion
- Predecessor based deletion
- Dangling references
🧠 Quick Check
See what you remember from the summary.
Which best describes the structural difference between singly and doubly linked nodes?
🧠 Flashcards Preview
Tap a card to reveal the definition.
Ready to quiz yourself?
Test what you remember with a full practice quiz on this note. Create a free account and start in seconds.
Full Notes
Read the original note content before deciding whether to save or study from it.
Linked Lists: Nodes and Links
📘 Overview A linked list stores elements in nodes connected by references rather than in contiguous array positions. Its structure supports efficient local insertion and deletion, but locating a node usually requires sequential traversal.
🧠 Key Idea Each node combines stored data with links that define the list's order. Changing the list means updating those links while preserving access to every node that should remain.
⚔️ Core Details: - A singly linked node contains a data field and a next reference to its successor. - The head references the first node; an empty list has a null head. - In a null-terminated list, the final node's next reference is null. - A doubly linked node stores both next and previous references for bidirectional traversal. - Insertion after a known node p sets new.next = p.next before setting p.next = new. - Deleting the successor of node p sets p.next = p.next.next when that successor exists.
🎯 Why It Matters: - Linked lists avoid shifting later elements during local insertions and deletions. - Sequential access and pointer overhead often make linked lists less suitable than arrays for frequent indexed reads. - Incorrect link updates can lose access to nodes or create unintended cycles. - Manual memory management requires deallocating removed nodes without leaving dangling references.
🧠 Quick Recall: - Node - a record containing data and one or more references to other nodes. - Head and tail - references to the first and last nodes; a tail reference is optional. - Traversal - following links from node to node; worst-case indexed access takes
More ways to study when you copy this note
Copy this note into your library to unlock focused practice sessions and long-term review.
Answer all questions first, then see feedback at the end — the way real exams work.
Focuses each session on what you got wrong, not what you already know.
Full timed exam with all questions, no pausing, and results at the end. Built for board exam prep.
Part of 🗄️ BS Information Systems — 1st Year
Browse this Review Set →More Computer Engineering notes
See all →More in Data Structures and Algorithms
See all →More from NoteLib
Browse NoteLib's public notes →Copy this note to your library and get the full Study Pack instantly — summary, key concepts, and practice quiz included.