Linked List Data Structure
Welcome !! In this blog, we will be learning about Linked List.
In this software world, Data storage has always been a very big battle and there are so many solutions regarding that. And when it comes to organizing the data, there are so many tools that do the job. Choosing the perfect tool for our job is the trick.
When it comes to organizing the data, the first thing that we come across is Data Structures. There are other different ways that we can store or organize our data; Trees, arrays, hashes, Graphs, stacks, queues are all types of data structures. One such Data Structure is Linked List. Let’s see what the Linked list is all about.
Read this to know more about Binary Tree Data Structures.
A Linked List is a linear Data Structure, in which Elements are not stored in contiguous memory allocations. In a linear Data Structure, data is stored in a sequence and in order to how they are constructed and traversed. In a linked list, in order to get to the end of the list, we have to go through all of the items in the list in order, or sequentially. Whereas, in a non-linear Data Structure, data don't have to be arranged in an order which means that we could traverse the data non-sequentially.
Memory management
The major difference between arrays and Linked List is the memory usage. When an array is created, which had 6 letters, it needs a certain amount of memory. We would need 6 bytes of memory in order to represent that array. We would need all of that memory in one contiguous block. That is to say, our computer would need to locate 7 bytes of memory that was free, one byte next to the another, all together, in one place.
Whereas in the Linked list, it doesn’t need all the 6 bytes of memory in one contiguous block. One byte could live somewhere, while the next byte could be stored in another place in memory altogether! Linked lists don’t need to take up a single block of memory; instead, the memory that they use can be scattered throughout.
The fundamental difference between arrays and linked lists is that arrays are static data structures, while linked lists are dynamic data structures.
Parts of Linked Lists
A linked list consists of nodes where each node contains a data field and a reference(link) to the next node in the list. The starting point of the Linked List is known as head. Without a head, you would not know where to start. S nearly almost all the Linked Lists must have ahead. The pointer of the last node points to null.
A single node is also pretty simple. It has just two parts: data, or the information that the node contains, and a reference to the next node.
Key Takeaways:
- A node only knows about what data it contains, and who its neighbor is.
- Almost all the Linked List has a head node by which we come to know where to start.
- The last node of Linked List points to null.
Types of Linked Lists
There are totally 3 types of Linked List. The parts of a linked list don’t change in any of these, but the way we structure our linked list can be quite different. Each type can solve certain problems.
Singly Linked Lists are based on the fact that they only go in one direction and these are the simplest type of linked list. To traverse through a singly linked list, we have to start at the head node and traverse from the head until the last node, which will end at an empty null value.
In Doubly Linked List, a node can refer to its subsequent neighbor node and it can also have a reference pointer to its preceding node, too! This can be helpful if we wanted to be able to traverse our data structure not just in a single track or direction, but also backward, too.
Read this to know more about Doubly Linked List
A circular linked list is a little odd in that it doesn’t end with a node pointing to a null value. Instead, it has a node that acts as the tail of the list (rather than the conventional head node), and the node after the tail node is the beginning of the list. This structure makes it really easy to add something to the end of the list, because you can begin traversing it at the tail node, as the first element and last element point to one another.
Read this to know more about Circular Linked Lists
Conclusion:
In this blog, we have seen about Linked List, their memory allocation, and also how linked lists are different from arrays. We have also seen the types of Linked Lists and their pictorial representation.
