LinkedList in Java
Linked lists are among the simplest and most common data structures . Arrays and Linked lists are similar since they both store collections of data. An array allocates memory for all its elements lumped together as one block of memory. In contrast, a linked list allocates space for each element separately in its own block of memory called a Node. The main disadvantage of using arrays to store data is that arrays are static structures and therefore cannot be easily extended or reduced to fit the data set. One disadvantage of a linked list over an array is that it does not allow direct access to the individual elements. If you want to access a particular item then you have to start at the head and follow the link until you get to that item.
Linked list is a data structure consisting of a group of nodes which together represent a sequence. It is dynamic in nature which allocates the memory when required. That means, the number of nodes in a list is not fixed and can grow and shrink on demand. Any application which has to deal with an unknown number of objects is a must to use a linked list. Each node in a Linked list contains two fields: a "data" field to store whatever element type the list holds for its client, and a "next" field which is a pointer used to link one node to the next node. The last node in the list has its .next field set to NULL to signify the end of the list.
There are three types of linked-list. They are:
- Single Linked List
- Doubly Linked List
- Circular Linked List
Doubly LinkedList : In a doubly linked list, each node contains two links the first link points to the previous node and the next link points to the next node in the sequence. Unlike single linked-list, items can be navigated forward and backward in a doubly linked list.
Circular LinkedList : In a circular linked list Last item contains link of the first element as next and the first element has a link to the last element as previous.
The following Java program illustrates several of the methods supported by this LinkedList collection Framework