Linked Lists

The term “List” refers to a linear collection of data items. The property of being sequential is basic to its definition and use.

A Linear Structure has two properties:

Property 1:

Each element is ‘followed by’ at most one other element

Property 2: No two elements are ‘followed by’ the same element. We generally write linear Data types like this

·

Counter example 1 (violating Property 1) : A points to B and C

·

Counter example 2 (violating Property 2): A and B both points to C,

Counter example 1 is a tree, but counter example 2 is not. If we drop both constraints we get a graph. In a graph there is no constraints on the relations we can define.

Linear lists can be divided into two categories: general and restricted.

In a general list , data can be inserted and deleted anywhere and there are no restrictions on the operations that can be used to process the list. General structures can be further described by their data, as either random or ordered lists. In a random or unordered list, there is no ordering of the data. In an ordered list , the data are arranged according to a key. A key is one or more fields within a structure that are used to identify the data. In the simple array, the data are also the keys. In an array of records structure, the key is a field, such as employee number, that identifies the record.

In a restricted list, data can only be added or deleted at the ends of the structure and processing is restricted to operations on the data at the ends of the list. Three restricted list structures are: the last in-first out (LIFO) Stack, the First in-First out (FIFO) queue, and deque structures. Four operations are generally associated with linear lists: insertion, deletion, retrieval and traversal. The first three apply to all lists, list traversal is not applicable to restricted lists.

Linked Lists

A linear linked list (or linked list, for short) or one-way list or singly linked list, is a linear sequence of data elements in which each node, except the last, links to a successor node by means of a pointer. Figure 3 shows a linked list, pHead, that contains four elements. The link in the last element contains null pointer, indicating the end of the list. We define an empty linked list to be null head pointer.

Data elements in a linked list are traditionally called nodes. A node in a linked list is a structure that has at least two fields: one contains the data, the other link or pointer or address of the next node in the sequence. Pointers are used to establish links between nodes in sequence. Therefore pointer is a data value that references a unit of storage.