CEG's Linux User Group

SINGLY LINKED LIST

Linked list is one of the fundamental data structures which can be used to implement other data structures.A linked list is essentially a collection of nodes.Each node consists of two fields. The first field, known as the data field holds the value or data and the second field, known as the address field holds the reference to the next node or is assigned NULL(if the linked list is empty). The main feature that distinguishes a linked list from an array and makes it advantageous is the fact that the elements in a linked list are not stored in contiguous memory locations(like array elements).

Technically speaking,linked lists can be defined as a collection of structures which need not be adjacent in the memory. Each structure contains the element and a pointer that points to its successor. This pointer is called the next pointer.

To access the linked list(entire list),it is common practice(though not a compulsion) to define a node called the header node. This header node like any other node has a data part which is usually assigned NULL and the address part that points to the first node (rather, the first element) in the list.

eg.

Linked lists can be broadly classified into:

• Singly linked list

• Circularly singly linked list

• Doubly linked list

• Circularly doubly linked list

  
  

  LINKED LIST OPERATIONS:

• Inserting a node in the beginning when the list is empty:

• Inserting a node in the beginning when the list is not empty:

• Inserting a node in the end(after the end node):

• Inserting a node in the middle:

For inserting a node in the middle, a temp node is used(just like a temporary variable in C).The address of header is transferred to temp node. We can get the data from first node using temp->element. To get data from second node, we shift temp to the second node. Now we can get the data from second node. Also,the position where the new node is to be inserted is obtained from the user to insert a new node in the middle in a linked list.

• Deleting a node in the beginning:

Deleting a node from linked list is relatively easy. First, we create node temp and transfer the address of header to temp.So transfer the address of temp->next to header so that it is now pointed to the second node. Now free the space allocated for first node.

• Deleting a node in the end:

The address field of the last node of the linked list always points to NULL. So when we delete the last node, the previous node to the last node should be made to point at NULL. So, we will track last node and previous node of the last node in the linked list to delete the last node.

• Deleting a node in the Middle:

To delete a node from the middle,the element of the node to be deleted is obtained from the user and linked list is traversed till the node before the node to be deleted. This node is now the temp node(using which the deletion is done by entering the appropriate code).