Last active
February 9, 2019 14:23
-
-
Save anoited007/c1bdaae802e2c970ad40a37fabe207bb to your computer and use it in GitHub Desktop.
The abstraction and implementation of both singly and doubly LinkedList
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package LinkedListPkg; | |
public class DblLinkedList<T> implements IDblLinkedList<T> { | |
private DblNode<T> head, next, prev, tail; | |
private int size; | |
public DblLinkedList(){ | |
head = null; | |
next = null; | |
prev = null; | |
tail = null; | |
size = 0; | |
} | |
public DblLinkedList(DblNode<T> head){ | |
this.head = head; | |
next = null; | |
prev = null; | |
tail = null; | |
size = 1; | |
} | |
public DblNode<T> getHead() { | |
return head; | |
} | |
public void setHead(DblNode<T> head) { | |
this.head = head; | |
} | |
public DblNode<T> getTail() { | |
return tail; | |
} | |
public void setTail(DblNode<T> tail) { | |
this.tail = tail; | |
} | |
public DblNode<T> getNext() { | |
return next; | |
} | |
public void setNext(DblNode<T> next) { | |
this.next = next; | |
} | |
public DblNode<T> getPrev() { | |
return prev; | |
} | |
public void setPrev(DblNode<T> prev) { | |
this.prev = prev; | |
} | |
public int getSize() { | |
return size; | |
} | |
@Override | |
public void addFirst(DblNode<T> node) { | |
if(head == null){ | |
this.head = node; | |
size++; | |
} | |
else { | |
DblNode<T> temp = head; | |
head = node; | |
head.setNext(temp); | |
temp.setPrev(node); | |
node.setPrev(null); | |
size++; | |
} | |
} | |
@Override | |
public void addAtPos(DblNode<T> node, int position) throws IndexOutOfBoundsException { | |
// setting counter to 1 because the first node is taken care of as a special scenario. | |
int counter = 1; | |
//Separating the error messages to provide a more meaningful error messages. | |
if (position < 0) { | |
throw new IndexOutOfBoundsException("The position entered is less than 0. Enter a value between 0 and " + size + "."); | |
} else if (position > size) { | |
throw new IndexOutOfBoundsException("The position specified is more than the size of the list. " + "Enter a value between 0 and " + size + "."); | |
} else { | |
if (position == 0) { | |
addFirst(node); //add first already increases the size of the list so no need to increase it again. | |
} | |
/* | |
* If position is equal to size plus one, it means we are trying to add to the end of the list so we just | |
* call addLast method. | |
*/ | |
else if(if position == size + 1) { | |
addLast(node); | |
} | |
else { | |
// A temporary node keep track of the nodes | |
DblNode<T> temp = head.getNext(); | |
DblNode<T> prev = head; | |
while ((temp.hasNext())) { | |
if (counter == position) { | |
prev.setNext(node); | |
node.setPrev(prev); | |
node.setNext(temp); | |
} | |
counter++; | |
prev = temp; | |
temp = temp.getNext(); | |
} | |
size++; | |
} | |
} | |
} | |
@Override | |
public void addLast(DblNode<T> node) { | |
DblNode<T> temp = tail; | |
temp.setNext(node); | |
tail = node; | |
tail.setPrev(temp); | |
size++; | |
} | |
@Override | |
public DblNode<T> removeFirst() { | |
DblNode<T> removedNode = head; | |
DblNode<T> newHead = head.getNext(); | |
head = null; | |
this.head = newHead; | |
newHead.setPrev(null); | |
size--; | |
return removedNode; | |
} | |
@Override | |
public DblNode<T> removeAtPos(int position) { | |
int counter = 1; | |
DblNode<T> removedNode = null; | |
if (position < 0) { | |
throw new IndexOutOfBoundsException("The position entered is less than 0. Enter a value between 0 and " + size + "."); | |
} else if (position > size) { | |
throw new IndexOutOfBoundsException("The position specified is more than the size of the list. " + "Enter a value between 0 and " + size + "."); | |
} | |
else { | |
if (position == 0) { | |
removeFirst(); | |
size--; | |
} | |
else if(position == size -1) removeLast(); | |
else { | |
// A temporary node keep track of the nodes | |
DblNode<T> temp = head.getNext(); | |
DblNode<T> prev = head.getPrev(); | |
while ((temp.hasNext())) { | |
if (counter == position) { | |
prev.setNext(temp.getNext()); | |
removedNode = temp; | |
temp = null; | |
size--; | |
} | |
} | |
} | |
return removedNode; | |
} | |
} | |
@Override | |
public DblNode<T> removeLast() { | |
DblNode<T> temp = tail; | |
DblNode<T> removedNode = null; | |
DblNode<T> prev = temp.getPrev(); | |
removedNode = tail; //assign the old tail to the removed node object. | |
tail = prev; //assign the prev of old tail as the new tail | |
tail.next = null; //assign the next of the new tail to null to remvoe reference to the old tail. | |
temp = null; // remove the previous tail | |
size--; | |
return removedNode; | |
} | |
@Override | |
public int size() { | |
return this.size; | |
} | |
@Override | |
public DblNode<T>[] empty() { | |
DblNode<T> temp = head; | |
DblNode<T>[] removedNodes = (DblNode<T>[]) new Object[size]; | |
//setting a counter to fill the array of removed nodes | |
int counter = 0; | |
if(this.size == 0) | |
System.out.println("The list is already empty"); | |
else if(this.size == 1) { | |
removedNodes[counter] = head; | |
head = null; | |
} | |
else{ | |
while(temp.hasNext()){ | |
DblNode<T> next; | |
removedNodes[counter] = temp; | |
/*assigning the next node to next variable before assigning to temp to avoid losing access to the next node. | |
* after setting temp to null. | |
*/ | |
next = temp.getNext(); | |
temp = null; | |
temp = next; | |
counter++; | |
} | |
} | |
this.size = 0; | |
return removedNodes; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class DblNode<T> { | |
private T data; | |
private DblNode<T> next; | |
private DblNode<T> prev; | |
public DblNode() { | |
data = null; | |
next = null; | |
prev = null; | |
} | |
public DblNode(T data) { | |
this.data = data; | |
next = null; | |
prev = null; | |
} | |
public T getData() { | |
return data; | |
} | |
public void setData(T data) { | |
this.data = data; | |
} | |
public DblNode<T> getNext() { | |
return next; | |
} | |
public void setNext(DblNode<T> next) { | |
this.next = next; | |
} | |
public DblNode<T> getPrev() { | |
return prev; | |
} | |
public void setPrev(DblNode<T> prev) { | |
this.prev = prev; | |
} | |
public boolean hasNext() { | |
return this.next != null; | |
} | |
public boolean hasPrev(){ | |
return this.prev != null; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public interface IDblLinkedList<T> { | |
// add a node to the beginning of the LinkedListPkg | |
void addFirst(DblNode<T> node); | |
// add a node to a position in the LinkedListPkg | |
void addAtPos(DblNode<T> node, int position) throws IndexOutOfBoundsException; | |
// add a node to the end of the Linked List | |
void addLast(DblNode<T> node); | |
// remove a node from the beginning | |
DblNode<T> removeFirst(); | |
//remove a node from a position | |
DblNode<T> removeAtPos(int position); | |
// remove a node from the end | |
DblNode<T> removeLast(); | |
//get size of the LinkedList | |
int size(); | |
//empty the linked list | |
DblNode<T>[] empty(); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package LinkedListPkg; | |
public interface ILinkedList<T> { | |
// add a node to the beginning of the LinkedListPkg | |
void addFirst(Node<T> node); | |
// add a node to a position in the LinkedListPkg | |
void addAtPos(Node<T> node, int position) throws IndexOutOfBoundsException; | |
// add a node to the end of the Linked List | |
void addLast(Node<T> node); | |
// remove a node from the beginning | |
Node<T> removeFirst(); | |
//remove a node from a position | |
Node<T> removeAtPos(int position); | |
// remove a node from the end | |
Node<T> removeLast(); | |
//get size of the LinkedList | |
int size(); | |
//empty the linked list | |
Node<T>[] empty(); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package LinkedListPkg; | |
public class LinkedList<T> implements ILinkedList<T> { | |
private Node<T> head; | |
private int size = 0; | |
public LinkedList(Node<T> head) { | |
this.head = head; | |
size++; | |
} | |
public LinkedList() { | |
head = null; | |
} | |
public Node<T> getHead() { | |
if(size > 0) | |
return head; | |
else | |
return null; | |
} | |
public void setHead(Node<T> head) { | |
this.head = head; | |
} | |
public int size() { | |
return this.size; | |
} | |
@Override | |
public void addFirst(Node<T> node) { | |
if(head == null) this.head = node; | |
else { | |
Node<T> temp = head; | |
head = node; | |
head.setNext(temp); | |
size++; | |
} | |
} | |
@Override | |
public void addAtPos(Node<T> node, int position) throws IndexOutOfBoundsException { | |
// setting counter to 1 because the first node is taken care of as a special scenario. | |
int counter = 1; | |
//Separating the error messages to provide a more meaningful error messages. | |
if (position < 0) { | |
throw new IndexOutOfBoundsException("The position entered is less than 0. Enter a value between 0 and " + size + "."); | |
} else if (position > size) { | |
throw new IndexOutOfBoundsException("The position specified is more than the size of the list. " + "Enter a value between 0 and " + size + "."); | |
} else { | |
if (position == 0) { | |
addFirst(node); //addFirst does the size increment as well. | |
} else { | |
// A temporary node keep track of the nodes | |
Node<T> temp = head.getNext(); | |
/* using temporary variable temp to track previous nodes since this is a singly linked list. | |
* another approach could be to manipulate the counter.*/ | |
Node<T> prev = head; | |
while ((temp.hasNext())) { | |
if (counter == position) { | |
prev.setNext(node); | |
} | |
counter++; | |
prev = temp; | |
temp = temp.getNext(); | |
} | |
size++; | |
} | |
} | |
} | |
@Override | |
public void addLast(Node<T> node) { | |
Node<T> temp = head; | |
if(this.size() == 0){ | |
this.setHead(node); | |
} | |
else { | |
while (temp.hasNext()) { | |
temp = temp.getNext(); | |
if (!temp.hasNext()) { | |
temp.setNext(node); | |
size++; | |
} | |
} | |
} | |
} | |
@Override | |
public Node<T> removeFirst() { | |
Node<T> removedNode = head; | |
Node<T> newHead = head.getNext(); | |
head = null; | |
this.head = newHead; | |
size--; | |
return removedNode; | |
} | |
@Override | |
public Node<T> removeAtPos(int position) { | |
int counter = 1; | |
Node<T> removedNode = null; | |
if (position < 0) { | |
throw new IndexOutOfBoundsException("The position entered is less than 0. Enter a value between 0 and " + size + "."); | |
} else if (position > size) { | |
throw new IndexOutOfBoundsException("The position specified is more than the size of the list. " + "Enter a value between 0 and " + size + "."); | |
} else { | |
if (position == 0) { | |
removeFirst(); | |
size--; | |
} else { | |
// A temporary node keep track of the nodes | |
Node<T> temp = head.getNext(); | |
/* using temporary variable temp to track previous nodes since this is a singly linked list. | |
* another approach could be to manipulate the counter.*/ | |
Node<T> prev = head; | |
while ((temp.hasNext())) { | |
if (counter == position) { | |
prev.setNext(temp.getNext()); | |
removedNode = temp ; | |
temp = null; | |
size--; | |
} | |
} | |
} | |
return removedNode; | |
} | |
} | |
@Override | |
public Node<T> removeLast() { | |
Node<T> temp = head; | |
Node<T> removedNode = null; | |
while (temp.hasNext()) { | |
temp = temp.getNext(); | |
if (!temp.hasNext()) { | |
removedNode = temp; | |
temp = null; | |
size--; | |
} | |
} | |
return removedNode; | |
} | |
@Override | |
public Node<T>[] empty() { | |
Node<T> temp = head; | |
Node<T>[] removedNodes = (Node<T>[]) new Object[size]; | |
//setting a counter to fill the array of removed nodes | |
int counter = 0; | |
if(this.size == 0) | |
System.out.println("The list is already empty"); | |
else if(this.size == 1) { | |
removedNodes[counter] = head; | |
head = null; | |
} | |
else{ | |
while(temp.hasNext()){ | |
removedNodes[counter] = temp; | |
temp = temp.getNext(); | |
counter++; | |
} | |
} | |
this.size = 0; | |
return removedNodes; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package LinkedListPkg; | |
public class Node<T> { | |
private T data; | |
private Node<T> next; | |
public Node(){ | |
data = null; | |
next = null; | |
} | |
public Node(T data){ | |
this.data = data; | |
next = null; | |
} | |
public T getData() { | |
return data; | |
} | |
public void setData(T data) { | |
this.data = data; | |
} | |
public Node<T> getNext() { | |
return next; | |
} | |
public void setNext(Node<T> next) { | |
this.next = next; | |
} | |
public boolean hasNext(){ | |
return this.next != null; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment