Link List (Howz it works)

22

Dec

A linked list is a collection of class objects called nodes. Each node is linked to its successor node in the list using a reference to the successor node. A node is made up of a field for storing data and the field for the node reference. The reference to another node is called a link. An example linked list is:

A major difference between an array and a linked list is that whereas the elements in an array are referenced by position (the index), the elements of a linked list are referenced by their relationship to the other elements of the array. From above example we can say that “Bread” follows “Milk”, not that “Bread” is in the second position. Moving through a linked list involves following the links from the beginning node to the ending node.
Another thing to notice that we mark the end of a linked list by pointing to the value null. Since we are working with class objects in memory, we use the null object to denote the end of the list.
Marking the beginning of a list can be a problem in some cases. It is common in many linked list implementations to include a special node, called the “header”, to denote the beginning of a linked list. The linked list in underlying figure is redesigned with a header node:

Insertion and Removal of an Item from Link List

Insertion becomes a very efficient task when using a linked list. All that is involved is changing the link of the node previous to the inserted node to point to the inserted node, and setting the link of the new node to point to the node the previous node pointed to before the insertion. In Figure (below) the item “Cookies” is added to the linked list after “Eggs”.

Removing an item from a linked list is just as easy. We simply redirect the link of the node before the deleted node to point to the node the deleted node points to and set the deleted node’s link to null. The diagram (below) we remove “Bacon” from the linked list.