Programming Tutorial

  Linked List | Set 3 (Deleting a node) We have discussed Linked List Introduction and Linked List Insertion in previous posts on a singly linked list. Let us formulate the problem statement to understand the deletion process.  Given a ‘key’, delete the first occurrence of this key in the linked list .  To delete a node from the linked list, we need to do the following steps.  1) Find the previous node of the node to be deleted.  2) Change the next of the previous node.  3) Free memory for the node to be deleted. Since every node of the linked list is dynamically allocated using malloc() in C, we need to call free() for freeing memory allocated for the node to be deleted. // A complete working C program  // to demonstrate deletion in  // singly linked list #include <stdio.h> #include <stdlib.h> // A linked list node struct Node { int data; struct Node *next; }; /* Given a reference (pointer to pointer) to the head of a list and an int, inserts a new node on the front of

  Linked List | Set 2 (Inserting a node) We have introduced Linked Lists in the  previous post . We also created a simple linked list with 3 nodes and discussed linked list traversal. All programs discussed in this post consider following representations of linked list .  // A linked list node  struct Node  {  int data;  struct Node *next;  };  In this post, methods to insert a new node in linked list are discussed. A node can be added in three ways  1)  At the front of the linked list  2)  After a given node.  3)  At the end of the linked list. Add a node at the front: (4 steps process)   The new node is always added before the head of the given Linked List. And newly added node becomes the new head of the Linked List. For example if the given Linked List is 10->15->20->25 and we add an item 5 at the front, then the Linked List becomes 5->10->15->20->25. Let us call the function that adds at the front of the list is push(). The push() must receive a pointer to the

  Linked List | Set 1 (Introduction) Like arrays, Linked List is a linear data structure. Unlike arrays, linked list elements are not stored at a contiguous location; the elements are linked using pointers. Why Linked List? Arrays can be used to store linear data of similar types, but arrays have the following limitations. 1)  The size of the arrays is fixed: So we must know the upper limit on the number of elements in advance. Also, generally, the allocated memory is equal to the upper limit irrespective of the usage. 2)  Inserting a new element in an array of elements is expensive because the room has to be created for the new elements and to create room existing elements have to be shifted. For example, in a system, if we maintain a sorted list of IDs in an array id[]. id[] = [1000, 1010, 1050, 2000, 2040]. And if we want to insert a new ID 1005, then to maintain the sorted order, we have to move all the elements after 1000 (excluding 1000). Deletion is also expensive with arrays un