What is link list
3 minute read
What is link list?
· A link list is a collection of data elements. It is called 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 it consists of two fields, one containing the item, and the other containing the address of the next item in the list.
· The following figure shows the structure of the node.
· A linked list is a collection of structures ordered by logical links that are stored as part of the data in the structure itself but not by their physical placement in memory.
· The link list is in the form of a pointer to another structure of the same type.
· The following figure shows the graphical representation of the link list.
Structure of node is represented as follows.
Struct tag_name
{
Type mamber1;
Type member2;
Struct tag_name *next;
};
Example
Struct node
{
int item;
struct node *next;
};
Advantages or disadvantages of link list.
Advantages:
· A link list is dynamic data structure.
· Link list can grow or shrink in size during execution of a program, as per the requirement.
· A link list can be made just as long as required.
· Link list doesn’t waste memory space it used the memory that is just needed for the list at any point of time.
· There is no need to specify the number of nodes to be used in the list.
· Link list provide flexibility is allowing the items to be rearrange efficiently.
· It is simple to insert or delete items by rearranging the links.
Disadvantages:
· The access to any arbitrary item is little and time consuming.
· Whenever we deal with a fixed length list it would be good to use an array rather than a link list.
· A link list uses more storage than an array with the same number of items.
List the types of link list.
The types of link list are,
Linear singly link list
Circular link list
Doubly link list
Circular doubly link list
Explain circular link list.
· The circular linked lists have no starting point and no ending point.
· The last item point back to the first item in the link list.
· The following figure shows graphical representation of the circular list.
· It allows traversing in the circular fashion.
· We can remove any of the nodes from the any node in one direction only.
Explain two-way doubly link list.
· The doubly link list uses double set of pointers.
· One pointing to the next item and other pointing to the preceding item.
· This allows us to traverse the list in either direction.
· In this node has three elememts
o LLINK: left link, points to the previous node.
o DATA; contains the data item.
o RLNK: right link, points to the next node.
· The following figure shows the graphical representation of the doubly link list.
· The LLINK and the RLINK of the first node and the last node contains the NULL as the value respectively.
Explain Circular doubly link list
· It is a combination of the circular linked list and the doubly linked list.
· In circular doubly linked list the node structure is same as the doubly linked list but the difference is that LLINK of the first node points to the last node and the RLINK of the last points to the first node.
· Circular doubly link list employee’s forward pointer and backward pointer in circular form.
Operations performed on linked list
The operations performed on linked list are,
a. Creating a list
b. Traversing the list
c. Counting the items in the list.
d. Printing the list (or sub list).
e. Looking up an item for editing or printing.
f. Inserting an item.
g. Deleting an item.
h. Concatenating two lists.