Linked Lists

The list manipulations demonstrated in program ListDemo are inefficient because data moves unnecessarily. The situation can be improved by having pointers to the records in arrays. Each record can include a field with the index of its successor, creating a linked list. If a record is deleted, the pointer of its predecessor is changed to the index of its successor. However, deletions result in unused space in the array. A good system would keep a list of free spaces in the array and reuse these as necessary. This is effective, but somewhat cumbersome. In the alternative approach demonstrated in program LinkedlistDemo, space is automatically created and released for you with lines of code such as new(PtrNew) and dispose(PtrFound).

The use of pointers to records means that pointers can be changed while keeping all the records in their original positions. For example, deletion is achieved by changing the next pointer of the deleted record's predecessor to point at its successor. A level courses include the theory of pointers and we encourage more use of them in coursework.

See the following demonstration programs to learn more.

Programming - a skill for life!

Introduction to lists (including arrays of records), linked lists, stacks and queues