{"id":27299,"date":"2022-04-08T01:23:48","date_gmt":"2022-04-07T19:53:48","guid":{"rendered":"https:\/\/python-programs.com\/?p=27299"},"modified":"2022-04-08T01:23:48","modified_gmt":"2022-04-07T19:53:48","slug":"linked-list-data-structure","status":"publish","type":"post","link":"https:\/\/python-programs.com\/linked-list-data-structure\/","title":{"rendered":"Linked List Data Structure"},"content":{"rendered":"
A linked list is a type of data structure that consists of a chain of nodes, each of which contains a value and a pointer to the next node in the chain.<\/p>\n
The list’s head pointer points to the first node, and the list’s last element points to null. The head pointer points to null when the list is empty.<\/p>\n
Linked lists can grow in size dynamically, and inserting and deleting elements from them is simple because, unlike arrays, we only need to change the pointers to the previous and next elements to insert or delete an element.<\/p>\n
Linked lists are commonly used in the construction of file systems, adjacency lists, and hash tables.<\/p>\n
Arrays can be used to store similar types of linear data, but they have the following limitations.
\n1) Because the array size is fixed, we must know the maximum number of elements in advance. Furthermore, regardless of usage, the allocated memory is always equal to the upper limit.
\n2) Inserting a new element in an array of elements is expensive because room must be made for the new elements, and existing elements must be shifted to make room, whereas in a linked list if we have the head node, we can traverse to any node through it and insert a new node at the required position.<\/p>\n
1)Dynamic Data Structure:<\/strong><\/p>\n 2)\u00a0No Memory Wastage:<\/strong><\/p>\n 3)Implementation:<\/strong><\/p>\n A Linked List can be used to easily implement some very useful data structures such as queues and stacks.<\/p>\n 4)Insertion and Deletion Operation:<\/strong><\/p>\n Insertion and deletion operations in a Linked List are simple because there is no need to shift every element after insertion or deletion. Only the address in the pointers needs to be changed.<\/p>\n 1)Memory Usage:<\/strong><\/p>\n A linked list requires more memory than an array because it includes a pointer field in addition to the data field. The pointer field, like all other fields, requires memory to store the address of the next node.<\/p>\n 2)Random Access:<\/strong><\/p>\n To get to node an at index x in a linked list, we must first go through all the nodes before it. In the case of an array, however, we can use arr[x] to directly access an element at index x.<\/p>\n 3)Reverse Traversal:<\/strong><\/p>\n A pointer to the first node of a linked list is used to represent it. The first node is referred to as the head. When the linked list is empty, the value of the head is NULL. <\/p>\n","protected":false},"excerpt":{"rendered":" Linked List Data Structure Why Linked List? Advantages of Linked Lists over arrays Disadvantages of Linked Lists over arrays Representation Linked List Data Structure: A linked list is a type of data structure that consists of a chain of nodes, each of which contains a value and a pointer to the next node in the …<\/p>\n\n
\n
Disadvantages of Linked Lists over arrays<\/h3>\n
\n
Representation:<\/h3>\n
\nA list node is made up of at least two parts:
\n1) data (we can store integers, strings, or any type of data).
\n2) A pointer to the next node (or a reference to it) (connects one node to another)<\/p>\n