Linked List : In order to overcome the shortcomings of the stack and the queue model,there was a need to create lists that can be manipulated easily for inserting a new element in a particular location or deleting a element in a list and so on.These operations must be done without affecting the other elements in a list (for ex. Stack involves popping out all the elements till a particular point if we need to insert something in between , which is a time consuming process and affects the other elements too)
Basically a linked list consists of a series of structures which are not adjacent in memory.These memory locations maybe random.Every structure has a element part and a address part that points to the next node.
And a Singly linked List can be represented by chaining these nodes together like
The last node has the NULL value ( 0 ) in it which marks the end of a linked list.
A typical singly linked list can be represented with the data and address fields grouped together in a node like this.The first node has the address of the second node and the second node has the address of the third node.This continues until the last node has the NULL value as the address stored in it.
Every node contains cue to the next.So even if one node is broken,the chain will be cut.
Insertion into a linked list :
To represent the insertion process,take a look at the figure below.The node X to be inserted follows this procedure :
1. The address field of the previous node P to the position in which the node X is to be inserted is pointed to node X
2. The address field of node X is pointed to the previously existing node Q (which was next to node P before insertion)
i.e.,
(Note : 0xF,0x3,0x2,0xA,0x4 represent the addresses of the nodes and can be random without sequence )
Deletion of node
In order to delete a node the following process is usually carried out.This is much simpler than insertion process.
1. The address field of the previous node is directly pointed to the next node of the node to be deleted.
2. The node to be deleted is freed of its memory space.
The graphical representation is
Click here to go to next part->
Basically a linked list consists of a series of structures which are not adjacent in memory.These memory locations maybe random.Every structure has a element part and a address part that points to the next node.
 |
| A node |
A typical singly linked list can be represented with the data and address fields grouped together in a node like this.The first node has the address of the second node and the second node has the address of the third node.This continues until the last node has the NULL value as the address stored in it.
Every node contains cue to the next.So even if one node is broken,the chain will be cut.
To represent the insertion process,take a look at the figure below.The node X to be inserted follows this procedure :
1. The address field of the previous node P to the position in which the node X is to be inserted is pointed to node X
2. The address field of node X is pointed to the previously existing node Q (which was next to node P before insertion)
i.e.,
Deletion of node
In order to delete a node the following process is usually carried out.This is much simpler than insertion process.
1. The address field of the previous node is directly pointed to the next node of the node to be deleted.
2. The node to be deleted is freed of its memory space.
The graphical representation is
Click here to go to next part->
No comments:
Post a Comment