Recent Posts

Thursday, 28 December 2017

Single Linked List Tutorial

What is a Linked List?
     A Linked list is a linear data structure that contains sequence of elements such that each element links to its next element in the sequence. Each element in a linked list is called as "Node". Each Node consists of its own data and the address of the next node and forms a chain.
     You have to start somewhere, so we give the address of the first node a special name called HEAD. Also, the last node in the Linked list can be identified because its next portion points to NULL.  A linked list has the following properties.
1. Successive elements are connected by pointers.
2. The last element points to NULL.
3. Can grow or shrink in size during execution of a program
4. Can be made just as long as required (until systems memory exhausts)
5. Does not waste memory space (but takes some extra memory for pointers). It allocates memory as list grows.
Linked Lists ADT
     The following operations make linked lists an ADT:
Main Linked Lists Operations
1. Insert: Inserts an element into the list.
2. Delete: Removes and returns the specified position element from the list.

Auxiliary Linked Lists Operations
1. Delete List: removes all elements of the list.
2. Count: returns the number of elements in the list.
3. Find nth node from the end of the list.

Why Linked Lists?
     There are many other data structures that do the same thing as Linked lists. Before discussing linked lists it is important to understand the difference between linked lists and arrays. Both linked lists and arrays are used to store collections of data, and since both are used for the same purpose, we need to differentiate their usage. That means in which cases arrays are suitable and in which cases linked lists are suitable.

Arrays Overview
What is an Array?

     An array is an indexed collection of fixed number of homogeneous data elements. The main advantage of array is we can represent multiple values under the same name. So that readability of the code will be improved. But the main disadvantage of array is fixed in size. i.e., once we created the array with some size then there is no chance of increasing or decreasing the size based on our requirement. Hence to use arrays compulsory we should know the size in advance which may not possible always. Hence memory point of view arrays not recommended to use. Using collections, we can resolve this problem.
     One memory block is allocated for the entire array to hold the elements of the array. The array elements can be accessed in constant time by using the index of the particular element as the subscript.
     To access an array element, the address of an element is computed as an offset from the base address of the array and one multiplication is needed to compute what is supposed to be added to the base address to get the memory address of the element. First the size of an element of that data type is calculated and then it is multiplied with the index of the element to get the value to be added to the base address. This process takes one multiplication and one addition. Since these two operations take constant time, we can say the array access can be performed in constant time.
For more details about Arrays Refer here Aarrays in Java

Advantages of Linked Lists
     Linked lists have both advantages and disadvantages. The advantage of linked lists is that they can be expanded in constant time. To create an array, we must allocate memory for a certain number of elements. To add more elements to the array when full, we must create a new array and copy the old array into the new array. This can take a lot of time.
     We can prevent this by allocating lots of space initially but then we might allocate more than we need and waste memory. With a linked list, we can start with space for just one allocated element and add on new elements easily without the need to do any copying and reallocating.

Disadvantages of Linked Lists 
     There are a number of issues with linked lists. The main disadvantage of linked lists is access time to individual elements. Array is random-access, which means it takes O(1) to access any element in the array. Linked lists take O(n) for access to an element in the list in the worst case. Another advantage of arrays in access time is spacial locality in memory. Arrays are defined as contiguous blocks of memory, and so any array element will be physically near its neighbors. This greatly benefits from modern CPU caching methods.
     Although the dynamic allocation of storage is a great advantage, the overhead with storing and retrieving data can make a big difference. Sometimes linked lists are hard to manipulate. If the last item is deleted, the last but one must then have its pointer changed to hold a NULL reference. This requires that the list is traversed to find the last but one link, and its pointer set to a NULL reference. Finally, linked lists waste memory in terms of extra reference points.

Single Linked List
     Generally Linked list means a singly linked list. This list consists of a number of nodes in which each node has a next pointer to the following element. The link of the last node in the list is NULL, which indicates the end of the list.  

     In any single linked list, the individual element is called as "Node". Every "Node" contains two fields, data and next (link) . The data field is used to store actual value of that node and next field is used to store the address of the next node in the sequence. The graphical representation of a node in a single linked list is as follows 
 
Note
1. In a single linked list, the address of the first node is always stored in a reference node known as "front" (Sometimes it is also known as "head").
2. Always next part (reference part) of the last node must be NULL. 
 

Basic Operations on a List
1. Traversing the list
2. Inserting an item in the list
3. Deleting an item from the list

1. Traversing the Linked List
     Let us assume that the head points to the first node of the list. To traverse the list, we do the following
1. Follow the pointers.
2. Display the contents of the nodes (or count) as they are traversed.
3. Stop when the next pointer points to NULL.
     The ListLength() function takes a linked list as input and counts the number of nodes in the list. The function given below can be used for printing the list data with extra print function. 

public class ListTraverse { 
  public int ListLength(ListNode headNode) { 
    int length = 0; 
    ListNode currentNode = headNode; 
    while(currentNode != null) { 
      length ++; 
      currentNode = currentNode.getNext(); 
    } 
  return length; 
  } 
} 
2.  Inserting an item in the list
     In a single linked list, the insertion operation can be performed in three ways. They are as follows.
1. Inserting at Beginning of the list
2. Inserting at End of the list
3. Inserting at Specific location in the list

1. Inserting at Beginning of the list
     In this case, a new node is inserted before the current head node. Only one next pointer needs to be modified (new node’s next pointer) and it can be done in two steps:
• Update the next pointer of new node, to point to the current head.
 • Update head pointer to point to the new node.
     The following function can be used for Inserting at Beginning of the list.
public synchronized void insertAtBegin (ListNode node) { 
   node.setNext(head); 
   head = node; 
   length ++; 
}
2. Inserting a Node in Singly Linked List at the Ending
     In this case, we need to modify two next pointers (last nodes next pointer and new nodes next pointer).
• New nodes next pointer points to NULL.
• Last nodes next pointer points to the new node.
3. Inserting a Node in Singly Linked List at the Middle.
     Let us assume that we are given a position where we want to insert the new node. In this case also, we need to modify two next pointers.
• If we want to add an element at position 3 then we stop at position 2. That means we traverse 2 nodes and insert the new node. For simplicity let us assume that the second node is called position node. The new node points to the next node of the position where we want to add this node.
• Position node’s next pointer now points to the new node.
Time Complexity: O (n). Since, in the worst we may need to insert the node at end of the list. 
Space Complexity: O (1), for creating one temporary variable.

3. Singly Linked List Deletion
     Similar to insertion, here also we have 3 cases.
1. Deleting the first node
2. Deleting the last node
3. Deleting an intermediate node.

1. Deleting the First Node in Singly Linked List
     First node (current head node) is removed from the list. It can be done in 2steps:
• Create a temporary node which will point to the same node as that of head.
• Now, move the head nodes pointer to the next node and dispose of the temporary node.
2. Deleting the Last Node in Singly Linked List
     In this case, the last node is removed from the list. This operation is a bit trickier than removing the first node, because the algorithm should find a node, which is previous to the tail. It can be done in 3 steps:
• Traverse the list and while traversing maintain the previous node address also. By the time we reach the end of the list, we will have two pointers, one pointing to the tail node and the other pointing to the node before the tail node.
• Update previous node’s next pointer with NULL.
• Dispose of the tail node.
3. Deleting an Intermediate Node in Singly Linked List
     In this case, the node to be removed is always located between two nodes. Head and tail links are not updated in this case. Such a removal can be done in two steps:
• Similar to the previous case, maintain the previous node while traversing the list. Once we find the node to be deleted, change the previous node’s next pointer to the next pointer of the node to be deleted.
• Dispose of the current node to be deleted.

Time complexity: O (n). In the worst we may need to delete the node at the end of the list.
Space Complexity: O (1). Since we are creating only one temporary variable. 

Next Tutorial : Doubly Linked Lists

Previous Tutorial : Recursion and Backtracking Tutorial 
 

1 comment: