An array is a very useful
data structure provided in various programming languages.
However, it has two limitations: (i) its size has to
be known at compilation time, and (ii) the data in the
array are separated in computer memory by the same distance.
This means that when you want to insert data into the
array you have to shift all the data in the array. These
limitations can be overcome by using linked structures.
A linked structure is a collection of nodes storing
information, and the location of other nodes. Nodes
can be located anywhere in memory, and passing from
one node to another can be done by storing the addresses
of other nodes in the linked structure. The most flexible
implementation is the use of pointers.
If a node contains a
data member that is a pointer to another node, then
many nodes can be strung together using only one variable
to access the entire chain of nodes. Such a chain of
nodes is the most frequently used implementation of
a linked list. A linked list is a data structure
composed of nodes, each node holding information, and
a pointer to another node in the list. If a node only
has the address to its successor in the chain, the list
is called a singly linked list.
