Just like a garland is made with flowers, a linked list is made up of nodes. We call every flower on this particular garland to be a node. And each of the node points to the next node in this list as well as it has data (here it is type of flower).
Singly linked lists contain nodes which have a data field as well as a next field, which points to the next node in the sequence. Operations that can be performed on singly linked lists are insertion, deletion and traversal.
head | | +-----+--+ +-----+--+ +-----+------+ | 1 |o-----> | 2 |o-----> | 3 | NULL | +-----+--+ +-----+--+ +-----+------+
Internal implementation of CPython, the frames and evaluated variables are kept on a stack.
For this we need to iterate only forward aur get the head, therefore singly linked-list is used.
Doubly linked lists contain node which have data field, next field and another link field prev pointing to the previous node in the sequence.
head | | +------+-----+--+ +--+-----+--+ +-----+------+ | | |o------> | |o------> | | | | NULL | 1 | | 2 | | 3 | NULL | | | | <------o| | <------o| | | +------+-----+--+ +--+-----+--+ +-----+------+
The browser cache which allows you to hit the BACK and FORWARD button. Here we need to maintain a doubly linked list, with URLs as data field, to allow access in both direction. To go to previous URL we will use prev field and to go to next page we will use next field.
Circular linked lists is a singly linked list in which last node, next field points to first node in the sequence.
head | | +-----+--+ +-----+--+ +-----+--+ —> | 1 |o-----> | 2 |o-----> | 3 |o----| +-----+--+ +-----+--+ +-----+--+
Timesharing problem solved by the operating system.
In a timesharing environment, the operating system must maintain a list of present users and must alternately allow each user to use a small portion of CPU time, one user at a time. The operating system will pick a user, let him/her use a small amount of CPU time and then move on to the next user.
For this application, there should be no NULL pointers unless there is absolutely no one requesting CPU time, i.e list is empty.
To add a new element to the list.
Insertion at the beginning:
Insertion in the middle/end.
Insertion after node X.
Time Complexity: O(1)
To delete existing element from the list.
Deletion at the beginning
Deletion in the middle/end.
Deletion after node X.
Time Complexity: O(1)
To travel across the list.
Time Complexity: O(n) // Here n is size of link-list
// Header files #include struct node < int data; struct node *next; >; // Head pointer always points to first element of the linked list struct node *head = NULL; // Display the list void printList() < struct node *ptr = head; // Start from the beginning while(ptr != NULL) < std::cout data next; > std::cout
// Insert link at the beginning void insertFirst(int data) < // Create a new node struct node *new_node = new struct node; new_node->data = data; // Point it to old head new_node->next = head; // Point head to new node head = new_node; std::cout
// Delete first item void deleteFirst() < // Save reference to head struct node *temp = head; // Point head to head's next head = head->next; // Free memory used by temp temp = NULL: delete temp; std::cout
// Find no. of nodes in link list void size() < int length = 0; struct node *current; for(current = head; current != NULL; current = current->next) < length++; >std::cout
// Find node with given data void find(int data) < // Start from the head struct node* current = head; // If list is empty if(head == NULL) < std::cout // Traverse through list while(current->data != data)< // If it is last node if(current->next == NULL) < std::cout else< // Go to next node current = current->next; > > // If data found std::cout
// Delete a node with given data void del(int data) < // Start from the first node struct node* current = head; struct node* previous = NULL; // If list is empty if(head == NULL)< std::cout // Navigate through list while(current->data != data)< // If it is last node if(current->next == NULL) < std::cout else < // Store reference to current node previous = current; // Move to next node current = current->next; > > // Found a match, update the node if(current == head) < // Change head to point to next node head = head->next; > else < // Skip the current node previous->next = current->next; > // Free space used by deleted node current = NULL; delete current; std::cout
class Node(object): # Constructor def __init__(self, data=None, next=None): self.data = data self.next = next # Function to get data def get_data(self): return self.data # Function to get next node def get_next(self): return self.next # Function to set next field def set_next(self, new_next): self.next = new_next class LinkedList(object): def __init__(self, head=None): self.head = head # Function to insert data def insert(self, data): # new_node is a object of class Node new_node = Node(data) new_node.set_next(self.head) self.head = new_node print("Node with data " + str(data) + " is created succesfully")
# Function to get size def size(self): current = self.head count = 0 while current: count += 1 current = current.get_next() print("Size of link list is " + str(count))
# Function to search a data def search(self, data): current = self.head found = False while current and found is False: if current.get_data() == data: found = True else: current = current.get_next() if current is None: print("Node with data " + str(data) + " is not present") else: print("Node with data " + str(data) + " is found")
# Function to delete a node with data def delete(self, data): current = self.head previous = None found = False while current and found is False: if current.get_data() == data: found = True else: previous = current current = current.get_next() if current is None: print("Node with data " + str(data) + " is not in list") elif previous is None: self.head = current.get_next() print("Node with data " + str(data) + " is deleted successfully") else: previous.set_next(current.get_next()) print("Node with data " + str(data) + " is deleted successfully")
Advantages
Disadvantages
We have to use free() in C and delete in C++ to free the space used by deleted node, whereas, in Python and Java free space is collected automatically by garbage collector.
