Copyright @ 2009 Ananda Gunawardena
Dynamically Allocated Lists
Concept of a linked list
Static arrays are structures whose size is fixed at compile time and therefore cannot be
extended or reduced to fit the data set. A dynamic array can be extended by doubling the
size but there is overhead associated with the operation of copying old data and freeing
the memory associated with the old data structure. One potential problem of using arrays
for storing data is that arrays require a contiguous block of memory which may not be
available, if the requested contiguous block is too large. However the advantages of using
arrays are that each element in the array can be accessed very efficiently using an index.
However, for applications that can be better managed without using contiguous memory
we define a concept called “linked lists”.
A linked list is a collection of objects linked together by references from one object to
another object. By convention these objects are named as nodes. So the basic linked list
is collection of nodes where each node contains one or more data fields AND a reference
to the next node. The last node points to a NULL reference to indicate the end of the list.
image source: Weiss Data Structures
The entry point into a linked list is always the first or head of the list. It should be noted
that head is NOT a separate node, but a reference to the first Node in the list. If the list is
empty, then the head has the value NULL. Unlike Arrays, nodes cannot be accessed by
an index since memory allocated for each individual node may not be contiguous. We
must begin from the head of the list and traverse the list sequentially to access the nodes
in the list. Insertions of new nodes and deletion of existing nodes are fairly easy to handle
and will be discussed in the next lesson. Recall that array insertions or deletions may
require adjustment of the array (overhead), but insertions and deletions in linked lists can
be performed very efficiently.
Types of Linked Lists
There are few different types of linked lists. A singly linked list as described above
provides access to the list from the head node. Traversal is allowed only one way and
there is no going back. A doubly linked list is a list that has two references, one to the
next node and another to previous node. Doubly linked list also starts from head node,
but provide access both ways. That is one can traverse forward or backward from any
node. A multilinked list (see figures 1 & 2) is a more general linked list with multiple
links from nodes. For examples, we can define a Node that has two references, age
pointer and a name pointer. With this structure it is possible to maintain a single list,