In my previous post I made a simple link list which holds integer values. Moving ahead in this post I am creating my own doubly link list .
A doubly-linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains two fields, called links, that are references to the previous and to the next node in the sequence of nodes.
The beginning and ending nodes' previous and next links, respectively, point to some kind of terminator, typically a sentinel node or null, to facilitate traversal of the list.
It can be conceptualized as two singly linked lists formed from the same data items, but in opposite sequential orders.
A doubly-linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains two fields, called links, that are references to the previous and to the next node in the sequence of nodes.
The beginning and ending nodes' previous and next links, respectively, point to some kind of terminator, typically a sentinel node or null, to facilitate traversal of the list.
It can be conceptualized as two singly linked lists formed from the same data items, but in opposite sequential orders.
A doubly-linked list whose nodes contain three fields: an integer value, the link to the next node, and the link to the previous node.
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 value
private int data;
//Reference(Pointer) to next node in list
private Node next;
//Reference(Pointer) to previous node in list
private Node prev;
public Node(int data) {
super();
this.data = data;
this.next = null;
this.prev = 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;
}
public Node getPrev() {
return prev;
}
public void setPrev(Node prev) {
this.prev = prev;
}
}
Implementation
package single;
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 specifed 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 first node i.e 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 specifed to insert node");
return false;
}
// Now we need to insert new node at this location
// so we will 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 is empty, can not eprform 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();
if(null != head.getNext()) {
head.getNext().setPrev(null);
head = head.getNext();
}
else {
head = null;
}
return deletedNodeValue;
}
@Override
public Integer deleteLast() {
// Check if list is already Empty
if (isEmpty()) {
System.out.println("List is empty, can not eprform delete operation");
return null;
}
Node currentNode = head;
// TODO
return null;
}
@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 specifed to delete node");
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 specifed to delete node");
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 do'nt want to execute this check twice by putting below
// isEmpty
// check at start of this method call
if (isEmpty()) {
System.out.println("List is empty, can not eprform 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 specifed to insert nodeInvalid Location specifed to insert node
Node you are trying to insert is null
Invalid Location specifed 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 ]
===========================delecefirst================================
List is: [11 4 3 2 1 54 55 53 56 44 52 45 43 46 21 22 23 24 31 32 33 34 ]
============================deleteloc================================
Invalid Location specifed to delete node
Invalid Location specifed 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 ]
============================deletethis(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 ]
============================deletelast================================
34
List is: [4 2 1 54 55 53 56 44 52 43 46 21 22 23 24 32 33 ]
No comments :
Post a Comment