Linked lists

After studying this section you should be able to:

• explain the concept of a linked list
• describe methods of representing a linked list
• describe the algorithms used to manipulate a linked list

Constructing and manipulating linked lists

A linked list will normally have a start pointer and nodes containing the data linked together:

Image

Linked lists offer a dynamic data store, they are not fixed size like arrays.

Let us assume that we wish to remove Node2 from the above. The first step is to change the pointer from Node1 to point at Node3:

Image

A language that supports dynamic data structures will have a Dispose operation.

The pointer from Node3 must now be made to point to the new node and the new node must point to Node4:

Image