Singly Linked list in Data Structures

  • A Singly Linked list is one in which all nodes are linked together in some sequential manner. Hence, it also called linear linked list. Clearly it has the beginning and the end.
  • The problem with this list is that we cannot access the predecessor of node from the current node. This can be overcome in doubly linked list.
  • A singly linked list is the simplest type of linked list in which every node contains some data and a pointer to the next node of the same data type.
  • By saying that the node contains a pointer to the next node, we mean that the node stores the address of the next node in sequence.
  • A singly linked list allows traversal of data only in one way.

Singly linked list

Traversing a Linked List

  • Traversing a linked list means accessing the nodes of the list in order to perform some processing on them.
  • Remember a linked list always contains a pointer variable START which stores the address of the first node of the list. End of the list is marked by storing NULL or –1 in the NEXT field of the last node.
  • For traversing the linked list, we also make use of another pointer variable PTR which points to the node that is currently being accessed.

Algorithm for traversing a linked list

 Step 1: [INITIALIZE] SET PTR = START
 Step 2: Repeat Steps 3 and 4 while PTR != NULL
 Step 3: Apply Process to PTR DATA
 Step 4: SET PTR = PTR NEXT
 [END OF LOOP]
 Step 5: EXIT
  • In this algorithm, we first initialize PTR with the address of START. So now, PTR points to the first node of the linked list.
  • Step 2, a while loop is executed which is repeated till PTR processes the last node, that is until it encounters NULL.
  • Step 3, we apply the process (e.g., print) to the current node, that is, the node pointed by PTR.
  • Step 4, we move to the next node by making the PTR variable point to the node whose address is stored in the NEXT field.

Inserting a New Node in a Linked List

In this section, we will see how a new node is added into an already existing linked list. We will take four cases and then see how insertion is done in each case.

  • The new node is inserted at the beginning.
  • The new node is inserted at the end.
  • The new node is inserted after a given node.
  • The new node is inserted before a given node.

Before we describe the algorithms to perform insertions in all these four cases, let us first discuss an important term called OVERFLOW. Overflow is a condition that occurs when AVAIL = NULL or no free memory cell is present in the system. When this condition occurs, the program must give an appropriate message.

Deleting a Node from a Linked List

In this section, we will discuss how a node is deleted from an already existing linked list. We will consider three cases and then see how deletion is done in each case.

  • The first node is deleted.
  • The last node is deleted.
  • The node after a given node is deleted.

Before we describe the algorithms in all these three cases, let us first discuss an important term called UNDERFLOW. Underflow is a condition that occurs when we try to delete a node from a linked list that is empty. This happens when START = NULL or when there are no more nodes to delete. Note that when we delete a node from a linked list, we actually have to free the memory occupied by that node. The memory is returned to the free pool so that it can be used to store other programs and data. Whatever be the case of deletion, we always change the AVAIL pointer so that it points to the address that has been recently vacated.

Algorithms