We know that a list refers to a set of items organized sequentially. An
array is an example of list. In an array, the sequential organization is
provided implicity by its index. We use the index for accessing and
manipulation of array elements . One major problem with the arrays is that the
size of an array must be specified precisely at the beginning. As pointed out
earlier, this may be a difficult task in many real-life applications.
A completely different way to represent a list is to make each item in the
part of a structure that also contains a "link" to the structure
containing the next item. This type of list is
called a linked list because it is a list whose order is given by
links from one item to the next.
Each structure of the list is called a node and consists of two
fields, one containig the item, and the other containing the address of the
next item(a pointer to the next item) in the list. A linked list is therefore a
collection of structures ordered not by their physical placement in memory
(like an array) but by logical links that are stored as part of the data in the
structure itself. The link is in the form of a pointer to another structure of
the same type.Such a structure is represented ads follows:
struct node
{
int item;
struct node *next;
} :
The first member is an integer item and the second a pointer to the next
node in the list as shown below. Remember,the item is an integer here only for
simplicity, and could be any complex data type.
A node may be represented in general form as follows :
Struct tag-name
{
type member1;
type member1;
………
……..
Struct tag-name *next;
}
The structure may contain more than one item with
different types. However, one of the items must be a pointer of the type
tag-name.
Types of Linked Lists
There are different types of lined lists. The linked lists are as follows:-
(1)Linear Singly Linked Lists
(2)Circular Linked Lists
(3)Two-way or doubly Linked Lists
(4)Circular doubly Linked Lists
No comments:
Post a Comment