Linked List Implementation

Linked List are non-primitive data structure that contains a collection unordered linked elements known as Nodes.

Linked List are linear data structure, which are not stored at a contiguous memory location.

Linked list consist of nodes where each node has two sub fields one part of the field is the data field and the other part is called the link field, which stores the address of the next node, each link field helps in linking nodes and form a linked list.

Linked list individual block

Struct Node {

   int data;
  Node* next; 

}

Why Linked list instead of arrays?

1. Size of the linked list are dynamic but in case of arrays size are fixed. No further extra element can be added after compilation.
2. Insertion of elements in array is dependent on the size of the array, In linked list insertion of elements are independent of the size.

Limitations
Extra space is needed for each node for the pointer field.
Random access not possible, list has to be traversed to access target element, except the first element.

Linked list are classified into three types...

• Single linked list : the type of list which has two field for each node one is the data field and other is the link field storing the address of the next node.

• Double linked list: the two way list in which each node has three fields, a field which stores the previous node, a field which stores the link for the next node and the data filed.

• Circular doubly linked list: Circular two way linked list, the circular doubly list does not contain NULL in the next field of the last node. The next field of the last node contain address of the first node of the list.

Linked list consist of head node which stores the link of the first node.

Language used : C++.

Basic Implementation

Inserting of Node to the List:: To add Node, we need to dynamically allocate memory for Node creation, In C++ to dynamically allocate memory we use new keyword.

To add Node to the list we need to pass the head reference and the value to inserted to the new Node.

Before we created Linked list individual block.

CODE

Node InsertNode(Node **head,int data ) {

Node *temp=new Node; 
temp->value=data;
temp->next=head;
head=temp;

}

• A pointer to node variable named temp is created.

• We initialize the value to data field.

• We initialize the Link field part by head value(which contains the address of the previous node).

• In the end head is pointed to newnode.

Hence Link created.

Traversing of Linked list: Traversal on Linked list is done from the head node(node which stores the link of the first node), when Null is encountered while traversing, the Linked list has reached to the end.

CODE

void print(Node *head)
{

Node *temp = *head;
cout << "List is   ";
while (temp != NULL)
{
    cout << temp->data << " ";
    temp = temp->next;
}

}

• A temp variable which takes the head node value.
• An iterative condition to traverse the list, until we reached to end.
• While we discover a node in the list we print its value.
• After printing the current Node value we update temp by pointing it to link field in the node.
• we repeat steps until we reach a node which points to NULL.

Hence we traverse the List.

"**head" means pointer to pointer, to modify a pointer reference of the pointer is passed.