Linked Lists and Nodes That Point
A singly linked list stores a sequence in nodes containing values and next references. Insertion after an already-known node needs two next-reference assignments. Access by position requires following links from the head.
What a learner can do afterwards
- Draw the pointer changes needed to insert and to delete a node in the middle
- Compare array access and ordered middle insertion with linked-list traversal and insertion after an already-known node
- Explain how null ends traversal and how another saved reference affects access to a detached tail
1 · Read
A singly linked list stores a sequence in nodes. Each node holds its own value and a next reference. Head refers to the first node; an empty list has null head. In a nonempty list, the last node's next is null. Head already identifies position one. Each next-reference step moves one position forward. Position numbers do not calculate node addresses as array indexes do.
Begin with 10 -> 20 -> 30 -> 40. To insert new node X after 20, set X.next to node 30, then set node 20's next to X. This preserves the route to the old tail. For a separate deletion, return to the original chain. Set node 20's next to node 40 to bypass node 30. Unlinking a node and releasing its memory are separate tasks.
At an already-known predecessor, insertion takes two next assignments and deletion takes one. Finding that predecessor may require a walk first. Array access by index takes fixed work; linked-list access from head needs more steps for farther positions. Inserting into the middle of a contiguous array while preserving order shifts later values. Removing the first linked node changes head instead of a predecessor's next.
Before changing a link, keep a reference to any tail you still need. Setting a middle node's next to null stops traversal from head at that node. The tail is detached from that walk. A separate saved reference into the tail can still reach it. If no such entry reference remains, the program loses access to the detached nodes.
Relinking at a known node takes fixed work. Finding a position needs a walk. Preserve a route to the tail before changing its link.
The lesson, questions and flashcards were written for this dataset.
The reading 'Preserving access while changing links' and the flashcards were written for this dataset.
More to read
Preserving access while changing links
A program can store a sequence without placing its values next to each other in memory. In a singly linked list, a reference called head identifies the first node. Each node stores a value and a next reference. Following those references gives the sequence. Null next marks its end; null head represents an empty list.
Suppose the values are 8, 17 and 25. To insert a new node containing 21 after 17, first make the new node refer to node 25. Then change node 17's next to the new node. The sequence becomes 8, 17, 21, 25. To remove 21 again, make node 17 refer directly to node 25. This changes which nodes belong to the chain. Releasing the removed node's memory is a separate matter.
Count locating and relinking separately. If the predecessor is already available, insertion takes two next-reference assignments. If only head is available, finding the predecessor may require following many links. Numbering positions does not remove that traversal. A contiguous array can calculate an element's address from its index, but ordered insertion into its middle shifts later entries.
Changing next to null ends the walk early. A separate reference into the detached tail can preserve access to it. Without another entry route, the program cannot reach those nodes even though their internal links may remain intact.
2 · Watch
به انگلیسیTake it off screen
Where it sits
Learn first
Optional connections
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.