Category: Entertainment

Presentation Description

linked list


Presentation Transcript




LINKED LIST Both Arrays and  Linked List  can be used to store linear data of similar types, but they both have some advantages and disadvantages over each other. Following are the points in favour of Linked Lists. (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, and in practical uses, upper limit is rarely reached. (2) Inserting a new element in an array of elements is expensive, because room has to be created for the new elements and to create room existing elements have to shifted. For example, suppose we maintain a sorted list of IDs in an array id[]. id[] = [1000, 1010, 1050, 2000, 2040, …..].


ADVANTAGES AND DRAWBACKS So Linked list provides following two advantages over arrays 1) Dynamic size 2) Ease of insertion/deletion Linked lists have following drawbacks: 1) Random access is not allowed. We have to access elements sequentially starting from the first node. So we cannot do binary search with linked lists. 2) Extra memory space for a pointer is required with each element of the list. 3) Arrays have better cache locality that can make a pretty big difference in performance.

Linked List | Set 2 (Inserting a node):

Linked List | Set 2 (Inserting a node ) 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: (A 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 head pointer, because push must change the head pointer to point to the new node




ROUTINES /* Given a reference (pointer to pointer) to the head of a list    and an int ,  inserts a new node on the front of the list. */ void push( struct node** head_ref , int new_data ) {     /* 1. allocate node */      struct node* new_node = ( struct node*) malloc ( sizeof ( struct node));        /* 2. put in the data  */      new_node ->data  = new_data ;        /* 3. Make next of new node as head */      new_node ->next = (* head_ref );        /* 4. move the head to point to the new node */     (* head_ref )    = new_node ; }

authorStream Live Help