![\"delete](\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Linked-list-in-DS-normla-image08.jpg\")
<\/a><\/p>\nvoid DeleteAtLast()\r\n{\r\n Node *ptr, *ptr1;\r\n ptr = head;\r\n while (ptr -> next != NULL)\r\n {\r\n ptr1 = ptr;\r\n ptr = ptr -> next;\r\n }\r\n ptr1 -> next =NULL;\r\n free ptr; \r\n}<\/pre>\nSearch node in Linked List<\/h3>\n
Searching for an element in the linked list. We compare the data of each node to the search element and return the location if found. If not found return -1.<\/span><\/p>\nBoolean flag= false;\r\nbool search(struct Node* head, int x)\r\n{\r\n struct Node* current = head;\r\n while (current != NULL)\r\n {\r\n if (current->key == x)\r\n {\r\n flag = true;\r\n break;\r\n }\r\n}\r\n return flag;\r\n}\r\n<\/pre>\nTraversing the linked list<\/h3>\n
Move the control pointer from the first node to the last node via each node in between and display data of each node.<\/p>\n
Int traverse(struct Node* head)\r\n{\r\n struct Node* current = head;\r\n while (current != NULL)\r\n {\r\n return current -> data;\r\n }\r\n}<\/pre>\nReversing a linked list<\/h3>\n
We need the head to point at the last node and the first node to point at NULL. In between all nodes will be pointing to their previous node in the original linked list.<\/p>\n
void reverse(struct Node** head)\r\n{\r\n struct Node* previous = NULL;\r\n struct Node* current = *head;\r\n struct Node* next = NULL;\r\n while (current != NULL) \r\n{\r\n next = current->next; \r\n current->next = previous;\r\n previous = current;\r\n current = next;\r\n }\r\n *head = previous;\r\n}<\/pre>\nLinked list implementation in C<\/h3>\n#include <stdio.h>\r\n#include <stdlib.h>\r\n \r\nstruct Node\r\n {\r\n int data;\r\n struct Node* next;\r\n};\r\n \r\nint main()\r\n{\r\n struct Node* Node1 = NULL;\r\n struct Node* Node2 = NULL;\r\n struct Node* Node3 = NULL;\r\n \r\n \r\n Node1 = (struct Node*)malloc(sizeof(struct Node));\r\n Node2 = (struct Node*)malloc(sizeof(struct Node));\r\n Node3 = (struct Node*)malloc(sizeof(struct Node));\r\n \r\n \r\n Node1 -> data = 1; \r\n Node1 -> next = Node2; \r\n \r\n Node2 -> data = 2;\r\n Node2 -> next = Node3;\r\n \r\n \r\n Node3 -> data = 3; \r\n Node3 -> next = NULL;\r\n \r\n display(Node1);\r\n return 0;\r\n}\r\n\r\nvoid display(struct Node* disp)\r\n{\r\n while (disp != NULL) \r\n{\r\n printf(\" %d \", disp -> data);\r\n disp = disp -> next;\r\n }\r\n}<\/pre>\nLinked list implementation in Python<\/h3>\nclass Node:\r\n def __init__(self, data):\r\n self.data = data \r\n self.next = None \r\n \r\nclass SinglyLinkedList: \r\n def __init__(self):\r\n self.head = None\r\n \r\n def DsiplayList(self):\r\n temp = self.head\r\n while (temp):\r\n print (temp.data)\r\n temp = temp.next\r\n \r\nif __name__=='__main__':\r\n \r\n sll = SinglyLinkedList()\r\n \r\n sll.head = Node(1)\r\n Node2 = Node(2)\r\n Node3 = Node(3)\r\n \r\n sll.head.next = Node2; \r\n Node2.next = Node3; \r\n \r\n llist.DisplayList()<\/pre>\nImplementation of Linked List in C++<\/h3>\n#include <bits\/stdc++.h>\r\nusing namespace std;\r\n \r\nclass Node {\r\npublic:\r\n int data;\r\n Node* next;\r\n};\r\n \r\nvoid displayList(Node* n)\r\n{\r\n while (n != NULL)\r\n {\r\n cout << n -> data << \" \";\r\n n = n -> next;\r\n }\r\n}\r\n \r\nint main()\r\n{\r\n Node* Node1 = NULL;\r\n Node* Node2 = NULL;\r\n Node* Node3 = NULL;\r\n \r\n Node1 = new Node();\r\n Node2 = new Node();\r\n Node3 = new Node();\r\n \r\n Node1 -> data = 1; \r\n Node1 -> next = Node2; \r\n \r\n Node2 -> data = 2; \r\n Node2 -> next = Node3;\r\n \r\n Node3 -> data = 3; \r\n Node3 -> next = NULL;\r\n \r\n displayList(Node1);\r\n \r\n return 0;\r\n}<\/pre>\nLinked list implementation in Java<\/h3>\nclass SinglyLinkedList\r\n {\r\n \r\nNode head; \r\n \r\n static class Node\r\n {\r\n int data;\r\n Node next;\r\n \r\n Node(int d)\r\n {\r\n data = d;\r\n next = null;\r\n } \r\n }\r\n \r\n \r\n public void DisplayList()\r\n {\r\n Node n = head;\r\n while (n != null) \r\n {\r\n System.out.print(n.data + \" \");\r\n n = n.next;\r\n }\r\n }\r\n \r\n public static void main(String[] args)\r\n {\r\n \r\n SinglyLinkedList sllist = new SinglyLinkedList();\r\n \r\n sllist.head = new Node(1);\r\n Node Node2 = new Node(2);\r\n Node Node3 = new Node(3);\r\n \r\n sllist.head.next =Node2; \r\n Node2.next = Node3; \r\n \r\n sllist.DisplayList();\r\n }\r\n}<\/pre>\nComplexity of Linked List<\/h3>\n
Space complexity: O(n)
\nTime complexity:<\/p>\n
\n\n\n| Operation<\/b><\/td>\n | Worst-case time complexity<\/b><\/td>\n<\/tr>\n\n| Search<\/span><\/td>\n | O(n)<\/span><\/td>\n<\/tr>\n\n| Insert<\/span><\/td>\n | O(1)<\/span><\/td>\n<\/tr>\n\n| Delete<\/span><\/td>\n | O(1)<\/span><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\nAdvantages of Linked List<\/h3>\n\n- Memory allocation takes place dynamically. A linked list can change the size, while an array has a fixed size.<\/span><\/li>\n
- Nodes in a linked list are non-contiguous stored, thus making efficient use of memory.<\/span><\/li>\n
- No empty node can be present in a linked list.<\/span><\/li>\n
- Nodes are created randomly in the memory, therefore, space utilization is highly optimized.<\/span><\/li>\n<\/ol>\n
Disadvantages of Linked List<\/h3>\n\n- Wastage of memory due to pointers.<\/span><\/li>\n
- Reverse traversing is not possible.<\/span><\/li>\n
- Accessing nodes at random is not possible.<\/span><\/li>\n<\/ol>\n
Array vs Linked list<\/h3>\n\n\n\n| Array<\/b><\/td>\n | Linked List<\/b><\/td>\n<\/tr>\n\n| Random access of elements in an array is possible.<\/span><\/td>\n | Random access of elements is not possible.<\/span><\/td>\n<\/tr>\n\n| Elements in an array are in a contiguous memory location.<\/span><\/td>\n | Elements in a linked list are at random in memory.\u00a0<\/span><\/td>\n<\/tr>\n\n| Memory allocation takes place at compile time.<\/span><\/td>\n | Memory allocation takes place during runtime.<\/span><\/td>\n<\/tr>\n\n| Array size is fixed.<\/span><\/td>\n | The size of a linked list is variable. It can add or remove nodes as and when required.<\/span><\/td>\n<\/tr>\n\n| Memory is allocated to the array in the stack section.<\/span><\/td>\n | Memory is allocated to the linked list in the heap section.<\/span><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\nApplications of Linked List<\/h3>\n1. Linked lists are used in programming requiring dynamic memory allocation.<\/span><\/p>\n2. Advance scientific calculations and numerical analysis using sparse matrices. The sparse matrix is represented by a linked list.<\/span><\/p>\n3. Linked list is useful for the implementation of stacks and queues.<\/span><\/p>\n4. Also used in reversing the functionality of the software.<\/span><\/p>\n5. Hash tables are created using linked lists. Hash table entries are implemented by a linked list.<\/span><\/p>\n6. Graphs use linked lists. If you want to represent graphs as an adjacency list, we use linked lists.<\/span><\/p>\n7. Polynomials can be represented with the help of linked lists. Each term in a polynomial has coefficient and power. Coefficient and power are stored as nodes and pointer points to the next node.<\/span><\/p>\nConclusion<\/h3>\nAfter going through this article, we now have some basic understanding of linked lists, some real-life examples of linked lists, how linked lists work, and types of linked lists. <\/span><\/p>\nWe also learned some basic operations on a linked list like adding nodes, deleting nodes. We will learn about doubly linked lists and circular linked lists in future articles.<\/span><\/p>\n","protected":false},"excerpt":{"rendered":"In computer science, we refer to the format of storing data on storage devices as a data structure. An array is the collection of data stored in contiguous memory locations. This makes accessibility very...<\/p>\n","protected":false},"author":1,"featured_media":95021,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[24020],"tags":[24332,24331,24335,24334,24330,8301,24333,24337,24336],"class_list":["post-94985","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-structure-tutorials","tag-applications-of-linked-list","tag-data-structures","tag-delete-node-in-linked-list","tag-insert-node-in-linked-list","tag-linked-list","tag-linked-list-in-data-structure","tag-operations-on-linked-list","tag-reversing-a-linked-list","tag-traversing-a-linked-list"],"yoast_head":"\n Linked List in Data Structure - DataFlair<\/title>\n<meta name=\"description\" content=\"A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. Learn more about it.\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/data-flair.training\/blogs\/linked-list-in-data-structure\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Linked List in Data Structure - DataFlair\" \/>\n<meta property=\"og:description\" content=\"A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. Learn more about it.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/data-flair.training\/blogs\/linked-list-in-data-structure\/\" \/>\n<meta property=\"og:site_name\" content=\"DataFlair\" \/>\n<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/DataFlairWS\/\" \/>\n<meta property=\"article:published_time\" content=\"2021-05-21T03:30:04+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Linked-list-in-DS.jpg\" \/>\n\t<meta property=\"og:image:width\" content=\"1200\" \/>\n\t<meta property=\"og:image:height\" content=\"628\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/jpeg\" \/>\n<meta name=\"author\" content=\"DataFlair Team\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@DataFlairWS\" \/>\n<meta name=\"twitter:site\" content=\"@DataFlairWS\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"DataFlair Team\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"11 minutes\" \/>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Linked List in Data Structure - DataFlair","description":"A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. Learn more about it.","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/data-flair.training\/blogs\/linked-list-in-data-structure\/","og_locale":"en_US","og_type":"article","og_title":"Linked List in Data Structure - DataFlair","og_description":"A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. Learn more about it.","og_url":"https:\/\/data-flair.training\/blogs\/linked-list-in-data-structure\/","og_site_name":"DataFlair","article_publisher":"https:\/\/www.facebook.com\/DataFlairWS\/","article_published_time":"2021-05-21T03:30:04+00:00","og_image":[{"width":1200,"height":628,"url":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Linked-list-in-DS.jpg","type":"image\/jpeg"}],"author":"DataFlair Team","twitter_card":"summary_large_image","twitter_creator":"@DataFlairWS","twitter_site":"@DataFlairWS","twitter_misc":{"Written by":"DataFlair Team","Est. reading time":"11 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/data-flair.training\/blogs\/linked-list-in-data-structure\/#article","isPartOf":{"@id":"https:\/\/data-flair.training\/blogs\/linked-list-in-data-structure\/"},"author":{"name":"DataFlair Team","@id":"https:\/\/data-flair.training\/blogs\/#\/schema\/person\/b49855299264df5e27e3ec6c2cd9fde9"},"headline":"Linked List in Data Structure","datePublished":"2021-05-21T03:30:04+00:00","mainEntityOfPage":{"@id":"https:\/\/data-flair.training\/blogs\/linked-list-in-data-structure\/"},"wordCount":1462,"commentCount":0,"publisher":{"@id":"https:\/\/data-flair.training\/blogs\/#organization"},"image":{"@id":"https:\/\/data-flair.training\/blogs\/linked-list-in-data-structure\/#primaryimage"},"thumbnailUrl":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Linked-list-in-DS.jpg","keywords":["Applications of linked list","Data Structures","Delete Node in Linked List","Insert node in Linked List","Linked List","linked list in Data Structure","Operations on Linked List","Reversing a Linked List","Traversing a Linked List"],"articleSection":["Data Structure Tutorials"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/data-flair.training\/blogs\/linked-list-in-data-structure\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/data-flair.training\/blogs\/linked-list-in-data-structure\/","url":"https:\/\/data-flair.training\/blogs\/linked-list-in-data-structure\/","name":"Linked List in Data Structure - DataFlair","isPartOf":{"@id":"https:\/\/data-flair.training\/blogs\/#website"},"primaryImageOfPage":{"@id":"https:\/\/data-flair.training\/blogs\/linked-list-in-data-structure\/#primaryimage"},"image":{"@id":"https:\/\/data-flair.training\/blogs\/linked-list-in-data-structure\/#primaryimage"},"thumbnailUrl":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Linked-list-in-DS.jpg","datePublished":"2021-05-21T03:30:04+00:00","description":"A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. Learn more about it.","breadcrumb":{"@id":"https:\/\/data-flair.training\/blogs\/linked-list-in-data-structure\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/data-flair.training\/blogs\/linked-list-in-data-structure\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/data-flair.training\/blogs\/linked-list-in-data-structure\/#primaryimage","url":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Linked-list-in-DS.jpg","contentUrl":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Linked-list-in-DS.jpg","width":1200,"height":628,"caption":"Linked list in Data Structure"},{"@type":"BreadcrumbList","@id":"https:\/\/data-flair.training\/blogs\/linked-list-in-data-structure\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Blog Home","item":"https:\/\/data-flair.training\/blogs\/"},{"@type":"ListItem","position":2,"name":"Data Structure Tutorials","item":"https:\/\/data-flair.training\/blogs\/category\/data-structure-tutorials\/"},{"@type":"ListItem","position":3,"name":"Linked List in Data Structure"}]},{"@type":"WebSite","@id":"https:\/\/data-flair.training\/blogs\/#website","url":"https:\/\/data-flair.training\/blogs\/","name":"DataFlair","description":"Learn Today. Lead Tomorrow.","publisher":{"@id":"https:\/\/data-flair.training\/blogs\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/data-flair.training\/blogs\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"https:\/\/data-flair.training\/blogs\/#organization","name":"DataFlair","url":"https:\/\/data-flair.training\/blogs\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/data-flair.training\/blogs\/#\/schema\/logo\/image\/","url":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2016\/07\/Data-Flair.png","contentUrl":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2016\/07\/Data-Flair.png","width":106,"height":48,"caption":"DataFlair"},"image":{"@id":"https:\/\/data-flair.training\/blogs\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/www.facebook.com\/DataFlairWS\/","https:\/\/x.com\/DataFlairWS","https:\/\/www.linkedin.com\/company\/dataflair-web-services-pvt-ltd\/","https:\/\/www.youtube.com\/user\/DataFlairWS"]},{"@type":"Person","@id":"https:\/\/data-flair.training\/blogs\/#\/schema\/person\/b49855299264df5e27e3ec6c2cd9fde9","name":"DataFlair Team","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/secure.gravatar.com\/avatar\/ef46b745ddad2fad690af626c6ef29b91809ad0a9f5ef398d07817d8cad042f5?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/ef46b745ddad2fad690af626c6ef29b91809ad0a9f5ef398d07817d8cad042f5?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/ef46b745ddad2fad690af626c6ef29b91809ad0a9f5ef398d07817d8cad042f5?s=96&d=mm&r=g","caption":"DataFlair Team"},"description":"DataFlair Team is a group of passionate educators and industry experts dedicated to providing high-quality online learning resources on programming, Java, Python, C++, DSA, AI, ML, data Science, Android, Flutter, MERN, Web Development, and technology. With years of experience in the field, the team aims to simplify complex topics and help learners advance their careers. At DataFlair, we believe in empowering students and professionals with the knowledge and skills needed to thrive in today\u2019s fast-paced tech industry. Follow us for Free courses, expert insights, tutorials, and practical tips to boost your learning journey.","url":"https:\/\/data-flair.training\/blogs\/author\/datafbdad\/"}]}},"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/posts\/94985","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/comments?post=94985"}],"version-history":[{"count":5,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/posts\/94985\/revisions"}],"predecessor-version":[{"id":95328,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/posts\/94985\/revisions\/95328"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/media\/95021"}],"wp:attachment":[{"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/media?parent=94985"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/categories?post=94985"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/tags?post=94985"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}} | | | | | | | | | |
![\"Linked](\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/05\/Linked-list-in-DS-normla-image01.jpg\")
<\/a><\/p>\n