Skip to content

Instantly share code, notes, and snippets.

@anoited007
Last active February 9, 2019 14:23
Show Gist options
  • Save anoited007/c1bdaae802e2c970ad40a37fabe207bb to your computer and use it in GitHub Desktop.
Save anoited007/c1bdaae802e2c970ad40a37fabe207bb to your computer and use it in GitHub Desktop.
The abstraction and implementation of both singly and doubly LinkedList
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;
}
}
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;
}
}
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();
}
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();
}
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;
}
}
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