linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a data and a reference (in other words, a link) to the next node in the sequence. This structure allows for efficient insertion or removal of elements from any position in the sequence.
A linked list whose nodes contain two fields: an integer value and a link to the next node. The last node is linked to a terminator used to signify the end of the list.
Linked lists are among the simplest and most common data structures. They can be used to implement several other common abstract data types, including lists (the abstract data type), stacks, queues, associative arrays.
A linked list whose nodes contain two fields: an integer value and a link to the next node. The last node is linked to a terminator used to signify the end of the list.
Linked lists are among the simplest and most common data structures. They can be used to implement several other common abstract data types, including lists (the abstract data type), stacks, queues, associative arrays.
Sections in this post: Link List Interface- Link List Node
- Implementation
Link List Interface
Below is my Link List Interface. It is not at all mandatory to write Interface for link list . I have written so as to make code more understandable and to follow good code writing practices.
public interface LLInterface {
/*
* different overloaded insert
*/
public boolean insertAtStart(Node nodeToInsert);
public boolean insertAtStart(int data);
public boolean insertAtEnd(Node nodeToInsert);
public boolean insertAtEnd(int data);
public boolean insert(Node nodeToInsert, int loc);
public boolean insert(int data, int loc);
/*
* different overloaded delete
*/
public Integer deleteFirst();
public Integer deleteLast();
public Integer delete(int loc);
public boolean deleteThis(int data);
/*
* ADT method to know if list is empty
* we will be using this method at many places such as
* before deleting a node to make sure list is already not empty
*/
public boolean isEmpty();
/*
* ADT method to print entire list
*
*/
public void printList(Node head);
/* ADT method to get number of nodes present after the given node.
*If head is passed as argument then it will return size of list
*This method should be avoided at places such as,
*to validate given insertion or deletion location as it
*internally traverse complete list once.
*/
public int getSize(Node head);
}
Link List Node
In Link list data is stored in nodes. therefore let's see how to implement a node. For the sake of simplicity I am considering nodes having only integer values but this can be changed easily.
public class Node {
// data variable will hold integer
private int data;
// Reference(Pointer) to next node
private Node next;
public Node(int data) {
super();
this.data = data;
this.next = null;
}
public Node() {
super();
}
/*
* Getter and setters
*/
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
Implementation
Now lets see how to implement link list. Whenever I am saying link list I am referring to singly link list. refer my other posts for Doubly link list and circular link list .
public class SLL implements LLInterface {
private Node head;
@Override
public boolean insertAtStart(Node nodeToInsert) {
/* Check if node is not null else return
* We add this check as there can be situation where object is set
* to null or some one has used default constructor make the node
* object etc.
*/
if (nodeToInsert == null) {
System.out.println("Node you are trying to insert is null");
return false;
}
// check if list is empty then set node as head
if (isEmpty()) {
head = nodeToInsert;
}
// make nodeToInsert as head and head as second
// node(nodeToInsert-->head-->....)
else {
nodeToInsert.setNext(head);
head = nodeToInsert;
}
return true;
}
@Override
public boolean insertAtStart(int data) {
/*
* we can have two approaches to get new node
*
* First Approach: Use default constructor and then set values
* using setters
* Node nodeToInsert = new Node();
* nodeToInsert.setData(data);
* nodeToInsert.setNext(null);
*
* Second approach: Use overloaded constructor of Node class
*/
Node nodeToInsert = new Node(data);
/* As we already have a method to insert node at beginning having
* node object as parameter we will just call that
* else we can add all the code of that method here itself
*/
return insertAtStart(nodeToInsert);
}
@Override
public boolean insertAtEnd(Node nodeToInsert) {
/* Check if node is not null else return
* We add this check as there can be situation where object
* is set to null or one has used default constructor make the node
* object etc.
*/
if (nodeToInsert == null) {
System.out.println("Node you are trying to insert is null");
return false;
}
// Check if list is empty then set node as head
if (isEmpty()) {
head = nodeToInsert;
return true;
}
Node currentNode = head;
while (currentNode.getNext() != null) {
currentNode = currentNode.getNext();
}
currentNode.setNext(nodeToInsert);
return true;
}
@Override
public boolean insertAtEnd(int data) {
/*
* we can have two approaches to get new node
* First Approach: Use default constructor and then set
* values using setters
* Node nodeToInsert = new Node();
* nodeToInsert.setData(data);
* nodeToInsert.setNext(null);
*
* Second approach: Use overloaded constructor of Node class
*/
Node nodeToInsert = new Node(data);
/* As we already have a method to insert node at end having
* node object as parameter we will just call that
* else we can add all the code of that method here itself
*/
return insertAtEnd(nodeToInsert);
}
@Override
public boolean insert(Node nodeToInsert, int loc) {
/* Check if node is not null else return
* We add this check as there can be situation where
* object is set to null or some one has used default constructor
* make the node object etc.
*/
if (nodeToInsert == null) {
System.out.println("Node you are trying to insert is null");
return false;
}
/* validate given location to add node, we wont check with list
* size here as it internally traverse complete list once
*/
if (loc < 1) {
System.out.println("Invalid Location specified to insert node");
return false;
}
if (loc == 1) {
insertAtStart(nodeToInsert);
} else {
Node currentNode = head;
/* Now we will reach the required location so that we can add
* node there.Note that we will stop one place before we want
* to add node and keep in mind current node is already at head
* e.g. if we want to add new node at location five, then we
* will traverse till node four.
* We will also check whether current node is not null
* as location given can be more then list size
*/
for (int i = 0; i < loc - 2 && currentNode != null; i++) {
currentNode = currentNode.getNext();
}
if (currentNode == null) {
System.out.println("Invalid Location specified to insert node");
return false;
}
/* Now we need to insert new node at this location.
* So we make new node's next to point to current node's next
* and current node will point to new node.
* Note that order is important here.
*/
nodeToInsert.setNext(currentNode.getNext());
currentNode.setNext(nodeToInsert);
return true;
}
return false;
}
@Override
public boolean insert(int data, int loc) {
/*
* we can have two approaches to get new node
*
* First Approach: Use default constructor and
* then set values using setters
*
* Node nodeToInsert = new Node();
* nodeToInsert.setData(data);
* nodeToInsert.setNext(null);
*
* Second approach: Use overloaded constructor of Node class
*/
Node nodeToInsert = new Node(data);
/* As we already have a method to insert node at end
* having node object as parameter we will just call that
* else we can add all the code of that method here itself
*/
return insert(nodeToInsert, loc);
}
@Override
public Integer deleteFirst() {
// Check if list is already Empty
if (isEmpty()) {
System.out.println("List empty,can not perform delete operation");
return null;
}
/* First save head value to return,then Make head to point next
* node in the list
* Again order is important
*/
int deletedNodeValue = head.getData();
head = head.getNext();
return deletedNodeValue;
}
@Override
public Integer deleteLast() {
//Check if list is already Empty
if(isEmpty()) {
System.out.println("List is empty, return null, can not perform delete operation");
return null;
}
if(head.getNext() == null) {
int deletedNode = head.getData() ;
head = null;
return deletedNode;
}
Node currentNode = head.getNext();
Node prevNode = head;
while(currentNode.getNext() != null) {
prevNode =currentNode;
currentNode = currentNode.getNext();
}
int deletedNode = currentNode.getData();
currentNode = null;
prevNode.setNext(null);
return deletedNode;
}
@Override
public Integer delete(int loc) {
/* validate given location to delete node,
* we wont check with list size here
* as it internally traverse complete list once
*/
if (loc < 1) {
System.out.println("Invalid Location specified to delete");
return null;
}
Node currentNode = head;
if (loc == 1) {
return deleteFirst();
}
/* we will also check whether current node is not null
* as location given can be can be more then list size
*/
for (int i = 0; i < loc - 2 && currentNode != null; i++) {
currentNode = currentNode.getNext();
}
if (currentNode == null) {
System.out.println("Invalid Location specified to delete");
return null;
}
int deletedNodeValue = currentNode.getData();
currentNode.setNext(currentNode.getNext().getNext());
return deletedNodeValue;
}
@Override
public boolean deleteThis(int data) {
if (head.getData() == data) {
return (deleteFirst()!= null);
}
/* Check if list is already Empty
* We are checking isEmpty after checking for head data as
* deleteFirst also has list empty check
* and we don't want to execute this check twice
* by putting below isEmpty check at start of this method call
*/
if (isEmpty()) {
System.out.println("List empty,can not perform delete operation");
return false;
}
Node currentNode = head;
//Iterate list until node to delete is reached or list ends
while (currentNode.getNext() != null) {
if (currentNode.getNext().getData() == data) {
currentNode.setNext(currentNode.getNext().getNext());
return true;
}
currentNode = currentNode.getNext();
}
System.out.println("data not present in the list");
return false;
}
/*
* This method will return true if List is Empty else false.
* List will be empty when head is null
*/
@Override
public boolean isEmpty() {
return null == head;
}
@Override
public void printList(Node head) {
if (head == null) {
System.out.println("Invalid node given");
return;
}
Node currentNode = head;
System.out.print("List is: [");
while (currentNode != null) {
System.out.print(" "+currentNode.getData());
currentNode = currentNode.getNext();
}
System.out.println(" ]");
}
public void printList() {
if (head == null) {
System.out.println("Invalid node given");
return;
}
Node currentNode = head;
System.out.print("List is: [");
while (currentNode != null) {
System.out.print(" "+currentNode.getData());
currentNode = currentNode.getNext();
}
System.out.println(" ]");
}
@Override
public int getSize(Node head) {
int count = 0;
Node currentNode = head;
while (currentNode != null) {
count++;
currentNode = currentNode.getNext();
}
return count;
}
public static void main(String[] args) {
SLL myLst = new SLL();
myLst.insert(new Node(41),0);
myLst.insert(new Node(42),2);
myLst.insert(new Node(43),1);
myLst.insert(new Node(44),1);
myLst.insert(new Node(45),2);
myLst.insert(new Node(46),4);
myLst.insert(null,3);
myLst.insert(51,0);
myLst.insert(52,2);
myLst.insert(53,1);
myLst.insert(54,1);
myLst.insert(55,2);
myLst.insert(56,4);
myLst.insertAtStart(1);
myLst.insertAtStart(2);
myLst.insertAtStart(3);
myLst.insertAtStart(4);
myLst.insertAtStart(new Node(11));
myLst.insertAtStart(new Node(12));
myLst.insertAtStart(new Node(13));
myLst.insertAtStart(new Node(14));
myLst.insertAtStart(null);
myLst.insertAtEnd(21);
myLst.insertAtEnd(22);
myLst.insertAtEnd(23);
myLst.insertAtEnd(24);
myLst.insertAtEnd(new Node(31));
myLst.insertAtEnd(new Node(32));
myLst.insertAtEnd(new Node(33));
myLst.insertAtEnd(new Node(34));
myLst.insertAtEnd(null);
myLst.printList(myLst.head);
System.out.println("=================deletefirst===============");
myLst.deleteFirst();
myLst.deleteFirst();
myLst.deleteFirst();
myLst.printList(myLst.head);
System.out.println("=========delete from location==============");
myLst.delete(0);
myLst.delete(1);
myLst.delete(30);
myLst.delete(2);
myLst.printList(myLst.head);
System.out.println("=========delete this(data)=================");
myLst.deleteThis(31);
myLst.deleteThis(131);
myLst.deleteThis(45);
myLst.printList(myLst.head);
}
}
If we run the program we will get output like this:
Output
==========================================================================
Invalid Location specified to insert nodeInvalid Location specified to insert node
Node you are trying to insert is null
Invalid Location specified to insert node
Node you are trying to insert is null
Node you are trying to insert is null
List is: [ 14 13 12 11 4 3 2 1 54 55 53 56 44 52 45 43 46 21 22 23 24 31 32 33 34 ]
===========================deletefirst=============================
List is: [ 11 4 3 2 1 54 55 53 56 44 52 45 43 46 21 22 23 24 31 32 33 34 ]
==========================delete from location========================
Invalid Location specified to delete node
Invalid Location specified to delete node
List is: [ 4 2 1 54 55 53 56 44 52 45 43 46 21 22 23 24 31 32 33 34 ]
==========================delete this(data)==========================
data not present in the list
List is: [ 4 2 1 54 55 53 56 44 52 43 46 21 22 23 24 32 33 34 ]
No comments :
Post a Comment