Data Structures And Algorithms (2 Part Series)
Hello There, My Gorgeous Friend On The Internet
This is the second part of my Data Structures and Algorithms series.
Check out First article For Introduction to Data Structures and Arrays.
In this post, First we'll talk about Linked List Data Structure, Why should we use it and simple java programs implementing Linked List.
Also, Check out my GitHub repository for all the programs:
So, the very first question that comes to my mind is:
What Is A Linked List?
- A linked list is a particular list of some data elements linked to one other. In this every element point to the next element which represents the logical ordering.
- Each element is called a 'node', which has two parts. DATA part which stores the information and POINTER which points to the next element.
- The first 'node' of the Linked List is called "head".
POINTER field of the last node is "null", which means it doesn't point to any element.
We can access a linked list using the address of the head node and then it gives us the address of the next node and so on. It's like a treasure hunt, you go to the first guy and you get the location of the next guy.
Why Linked List?
- And the answer is that Linked List is better than Arrays in terms of Space Complexity and in terms of Time Complexity.
- In arrays, we must know the maximum size of the array in advance because arrays are contiguous collection of elements. By contiguous, we mean the elements of the array are adjacent to one another in memory with no gaps between them.
- And thus, if we want to enter more elements than the size of an array, we need to create a new array of bigger size and then copy all the elements in this new array. This process is very time consuming and thus, not practical.
- Memory utilization is inefficient in the Array. Conversely, memory utilization is efficient in the Linked List.
Types Of Linked List
- Singly Linked List
- Doubly Linked List
- Circular Linked List
- Singly linked list is a basic linked list type. A singly Linked list is a collection of nodes linked together in a sequential way where each node of the singly linked list contains a data field and an address field that contains the reference of the next node.
Here is a simple program implementing a Linked List in Java.
Insertion Of Nodes In Linked List
There is a total of three possibilities of inserting a node in the linked list as below.
- Insertion of a node at the start of the linked list
- Insertion of a node at the end of the linked list
- Insertion of a node at a specific location in the linked list(i.e. after a given node.)
Here is a program that shows all three insertions in a linked list.
And now we'll see a full program with the implementation of the Linked List and also all possibilities of insertion of the node.
In the next article, we'll see more operations on a Linked List.
Thanks For Scrolling, Stick Around✌🏻.