Linked List

(426 Views)


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.

what is linked list simple explanation

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:

  1. 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.
  2. 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

  1. Singly linked list
  2. Circular linked list
  3. Doubly linked list
  4. 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. what is singly linked list simple explanation

Circular Linked List

Every element holds address of next element and the last element holds the address of first element forming a circular reference. what is circular linked list simple explanation

Doubly Linked List

Every element knows where next element is present and also where previous element is present. what is doubly linked list simple explanation

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.

what is doubly circular linked list simple explanation

Linked List Implementation in Java:

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); }

Solution Worked 1 UpvotesUpvote

        

Solution Didn't Worked 0 DownvotesDownvote



Comments



Search