Category LinkedList

Home › All Categories › LinkedList

LinkedList

A linked list is a sequence of values, like an array, stored a different way. An array keeps its elements side by side in one block of memory. A linked list keeps each element in its own small piece of memory, a node, and every node holds a link to the next one -- and, in this list, to the previous one as well.

Think of a train: you can couple a carriage onto either end without touching the others, and you get from one carriage to the next by walking through. What you cannot do is jump straight to carriage 37 -- you count your way there.

That trade is the point. Adding or removing at either end is quick however long the list is -- PushFront, PushBack, PopFront and PopBack -- which makes a LinkedList a natural queue (first in, first out) or stack (last in, first out). There is no [ i ] to reach an element by its position; you walk the list with for each.

The example below builds a two-item list from both ends, takes the front item off, and prints what is left:

#import "std/containers"
using containers

dim q as LinkedList( of ustring )

q.PushBack( "b" )
q.PushFront( "a" )

print q.PopFront( )                  ' "a"

for each s in q
    print s
next

A brace list fills one at the declaration: dim l as LinkedList( of long ) = { 1, 2, 3 } calls PushBack once per element. See Collection Initializers.

When To Use It

For a queue, reach first for a Deque: the same O(1) work at both ends, plus indexing, and no allocation per element.

Prefer Array unless one of these is what you actually need:

• O(1) insertion at the FRONT. Array.Insert( 0, v ) is O(n). - An iterator that STAYS VALID across insertions elsewhere in the list.

Every Array iterator is invalidated by a Push that reallocates.

Array is faster for everything else -- contiguous storage, no per-element allocation, and no pointer chasing.

Members

Count( ) as int32                               O(1)
IsEmpty( ) as boolean                           O(1)

PushFront( byref v as T )                       O(1)
PushBack( byref v as T )                        O(1)
PopFront( ) as T                                O(1)  removes and returns
PopBack( ) as T                                 O(1)  removes and returns
Front( ) byref as T                             O(1)
Back( ) byref as T                              O(1)

Clear( )                                        O(n)
GetIterator( ) as LinkedListIterator( of T )    O(1)

As a queue (FIFO):

q.PushBack( item )
dim next_ as T = q.PopFront( )

As a stack (LIFO):

q.PushBack( item )
dim top as T = q.PopBack( )

The Empty List

PopFront( ), PopBack( ), Front( ) and Back( ) on an empty list return a DEFAULT-CONSTRUCTED T. There is no error channel here and no exception to throw. Check IsEmpty( ) first if the difference matters:

while q.IsEmpty( ) = false
    process( q.PopFront( ) )
wend

Front( ) and Back( ) on an empty list return a reference to a shared blank -- a reference has to refer to something, and there is nothing else to refer to. Do not write through it.

Ownership AND Copying -- The Part That Matters

Unlike Array, Map and Set -- whose storage is a dynamic array field, so the language deep-copies and destroys it for free -- this holds RAW NODE POINTERS.

The compiler-supplied copy would duplicate the head and tail pointers and give two lists sharing one chain, which then double-frees. So the destructor, the copy constructor and 'operator let' are all written out by hand, and they are the reason this container's source is longer than it looks.

COPY AND ASSIGNMENT ARE DEEP:

dim b as LinkedList( of int32 ) = a       ' every node duplicated
b.PushBack( 99 )                         ' a is unchanged

c = a                                    ' old contents freed, then copied
c = c                                    ' self-assignment is safe

Self-assignment is guarded explicitly: without the check, 'operator let' would free the chain and then walk it.

A LinkedList( of T ptr ) frees the NODES, not the pointees.

Iterator Invalidation

This is the container's other reason to exist. Nothing detects a violation.

PushFront / PushBack                        iterators stay VALID
removing the node an iterator is on         that iterator invalidated
Clear                                       all iterators invalidated

Compare with Array, where any Push that reallocates invalidates everything.

Implementation

Doubly linked, with the value stored by copy in each node. 'new' and 'delete' on a generic instantiation, including a self-referential

as LinkedNode( of T ) ptr nxt, prv

field, are what make this possible.

PushFront and PushBack copy the value BEFORE allocating the node, so

q.PushFront( q.Back( ) )

means what it looks like: the argument refers into a list that is about to be restructured.

Sorting

#import "std/containers"

SortList( l )               ascending, by '<' on T
SortListBy( l, less )       ascending, by a comparer

A bottom-up merge sort over the node chain: O(n log n) worst case, O(1) extra memory, STABLE, and NO ELEMENT IS MOVED AT ALL -- the nodes are relinked, so sorting a LinkedList( of string ) touches no string. Copying the list into an Array, sorting that and copying it back is slower, not faster.

There is one list sort and it is the stable one. Introsort is not available here and the reason is structural: quicksort needs random access to reach its pivot and to scan inward from both ends, and a linked list gives neither.

See Sorting.

Source: pkg/std/containers/linkedlist.tiko

Tests

src/tests/generics/container-linkedlist.bas is exhaustive: every member, empty / one / many states, both ends, the single-element case where head and tail are the same node (and removing it must clear both, or the next push links onto a freed node), FIFO and LIFO drains, draining from alternating ends, pushing the list's own element, 10k nodes checked end to end in order, FOR EACH in both binding forms with exit/continue, element types including strings and a nested container, and destructor balance with a counting element type.

The copy and assignment section is load-bearing rather than a formality: it checks independence in BOTH directions after copy construction and after assignment, self-assignment, assigning an empty list over a full one, and copying an empty list.

API reference

Every entry, grouped by task. Collections lists them beside the rest of the area.

Choose a container

Function	What it does	From
LinkedList	Holds a chain of values that is quick to add to and remove from at either end.	std/containers
Deque	Holds a sequence that is quick to change at both ends and can be read by index.	std/containers

Sort an Array or a LinkedList

Function	What it does	From
SortList (LinkedList)	Sorts a LinkedList in ascending order by relinking nodes; equal elements keep order.	std/containers
SortListBy (LinkedList)	Sorts a LinkedList by your comparer, relinking nodes; equal elements keep order.	std/containers

Queues and stacks: LinkedList and Deque

Function	What it does	From
LinkedList.PushBack	Adds a value at the back of the list.	std/containers
LinkedList.PushFront	Adds a value at the front of the list.	std/containers
LinkedList.PopFront	Removes and returns the front value, or a default value if the list is empty.	std/containers
LinkedList.PopBack	Removes and returns the back value, or a default value if the list is empty.	std/containers
LinkedList.Front	Returns a reference to the front value without removing it.	std/containers
LinkedList.Back	Returns a reference to the back value without removing it.	std/containers
LinkedList.Count	Returns the number of values in the list.	std/containers
LinkedList.IsEmpty	Returns true if the list has no values.	std/containers
LinkedList.Clear	Removes every value and frees its nodes.	std/containers
Deque.PushBack	Adds a value at the back of the deque.	std/containers
Deque.PushFront	Adds a value at the front of the deque.	std/containers
Deque.PopFront	Removes and returns the front value, or a default value if the deque is empty.	std/containers
Deque.PopBack	Removes and returns the back value, or a default value if the deque is empty.	std/containers
Deque.TryPopFront	Removes the front value into a variable; returns false if the deque is empty.	std/containers
Deque.TryPopBack	Removes the back value into a variable; returns false if the deque is empty.	std/containers
Deque.Front	Returns a reference to the front value; the deque must not be empty.	std/containers
Deque.Back	Returns a reference to the back value; the deque must not be empty.	std/containers
Deque.At	Returns a reference to the value at a position, 0 being the front, like d[ i ].	std/containers
Deque.Count	Returns the number of values in the deque.	std/containers
Deque.IsEmpty	Returns true if the deque has no values.	std/containers
Deque.Clear	Removes every value but keeps the allocated room.	std/containers

Walk a container step by step

Function	What it does	From
LinkedList.GetIterator	Returns an iterator over the values that stays valid when others are added.	std/containers
LinkedListIterator	Holds a position in a LinkedList; it survives changes elsewhere in the list.	std/containers
Deque.GetIterator	Returns an iterator that walks the deque from front to back.	std/containers

Reserve room ahead of time

Function	What it does	From
Deque.Capacity	Returns how many values fit before the deque has to grow, always a power of two.	std/containers
Deque.Reserve	Makes room for at least n values without adding any.	std/containers

Check a container's internals

Function	What it does	From
LinkedNode	Holds one LinkedList value and the links to its neighbours; normal code never uses it.	std/containers

---

---

Home · Keyword Index