The linked list data structure is often used to implement other data structures.
What is Linked List?
A linked list is a sequence of nodes where each node stores its own data and a pointer (address) to the location of the next node.
One node links to another forming what can be thought of as a linked chain.
The last item in the list has a link to NULL, indicating the end of the chain.
Advantages:
Although a linked list is similar to an array, it is not restricted to a declared number of elements. Additionally, unlike an array which stores data contiguously in memory or on disk, a linked list can easily insert or remove elements without reallocation or reorganization of the entire structure because the data items need not be stored contiguously.
Linked List Drawbacks:
- Random access is not allowed. We must access nodes sequentially starting from the first one. Therefore, we cannot do a binary search on a linked list.
- Extra memory space for a link is required for each element of the list.
Types of Linked List:
There are 4 types of linked list. They are
- Singly linked list
- Circular linked list
- Doubly linked list
- Doubly circular linked list
Singly Linked List
Every element knows where the next element is present and the last element holds null representing end of the linked list.
Circular Linked List
Every element holds address of next element and the last element holds the address of first element forming a circular reference.
Doubly Linked List
Every element knows where next element is present and also where previous element is present.
Doubly Circular Linked List
Similar to double linked list whereas the last element holds the address of first link and first element holds the address of last link forming two circular references.
Linked List Implementation in Java:
<![CDATA[public class Node{
Private Node next; //pointer
Private int info; // information
public Node(int info){
this.info = info;
Next = null;//single node points
//to null
}
//getters and setters
public Node getNext(){
return next;
}
public void setNext(Node n){
Next = n;
}
public int getInfo(){
return info;
}
public void setInfo(int i){
Info = i;
}
//
}
public class LinkedList{
private Node header;//pointer
//to the first node
//of the list
public LinkedList(){
Header = null; /*header points to nothing because list is empty at first*/
}
public void add(int info){
//adds to the end of the list
Node n = new Node(info);
If(header==null)//if list is empty
header = n;
else{
/*a new pointer called current, that can be pointed to any node. header must remain pointing to the first node*/
Node current = header;/*current and header are now aliases pointing to the same node which is at the beginning of the list*/
while(current.getNext()!=null)
Current=current.getNext();/*moving the "current" pointer to the end of the list, so we can set the "next" attribute of the
last node to the node we're adding(e.i linking
the last node to the node we're adding)*/
current.setNext(n);//linking
}
}
public boolean deleteL(){/*removes a node from the end of the list, and returns true if node was successfully deleted*/
if(header == null)
return false;/*handling user logical errors if he decides to remove from an empty list*/
Node current = header;
while(current.getNext().getNext()!=null)
current = current.getNext();/*this will point "current" to the node right before the last*/
current.setNext(null);/*the node right before the last, is not pointing to the last node anymore.It is now pointing to null, leaving the last node to be collected by the garbage collector*/
return true;
}
public void addFirst(int info){
//adds to the beginning of the list
Node n = new Node(info);
If(header==null)//if list is empty
Header = n
else{
n.setNext(header);/*linking the new node to the first node of the list*/
header = n;/*header must remain pointing to the first node, so we repoint it to the new node added at the beginning*/
}
}
public boolean deleteFirst(){/*deletes the first node from the list*/
if(header == null)
return false;//handling user errors
if(size() == 1){
header = null;/*leaving the only node in the list unreferenced for the garbage collector*/
return true;
}
Node current = header.getNext();
header.setNext(null);
header = n;
return true;
}
public int size(){/*returns the size of
the list*/
if(header == null)//if empty
return 0;
int count = 0;
Node current = header;
while(current.getNext()!=null){
current = current.getNext();
count++;
}
return count;
}
public boolean insert(int info,int index){
/*inserts a node into the list with an index
to where we want to add it.And returns true
if "index" is valid*/
Node n = new Node(info);
if(index<0 || index>size())
return false;/*handling user illogical errors, in case he inputs an invalid index*/
if(header == null){/*if empty, then index must be 0, since it skipped the first if-statement*/
header = n;
return true;
}
if(index == 0){/*if index is at 0, and list is not empty, then we add the node to the beginning of the list*/
n.setNext(header);
header = n;
return true;
}
/*if none of the if-statements are true,
then */
Node current = header;
for(int i=0; i<(index-1); i++)
current = current.getNext();
n.setNext(current.getNext());
current.setNext(n);
return true;
}
public boolean remove(int index){
/*deletes a node at a specified index*/
if(index<0 || index>=size())
return false;
if(header == null)
return false;
if(index == 0){
header = header.getNext();
return true;
}
Node current = header;
for(int i=0; i<(index-1); i++)
current = current.getNext();
current.setNext(current.getNext().getNext());
return true;
}
}
public static void main(String[]args){
LinkedList list = new LinkedList();
list.add(10);
list.addFirst();
list.insert(20,1);
list.deleteL();
list.deleteFirst();
list.remove(0);
}]]>
1 Upvotes
0 Downvotes