Created
December 30, 2016 18:20
-
-
Save arrayed/c2ad7933c0fcc1990d07fd445eac799f to your computer and use it in GitHub Desktop.
Linked List Base List Implementation in Java
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
//============================================================================ | |
// Name : DLinkedList.java | |
// Author : Amritpal Singh | |
// Version : v0.1 | |
// Copyright : arrayed.net | |
// Description : Linked List Based List Implementation in Java | |
//============================================================================ | |
public class DLinkedList<E> { | |
protected int numElements; // number of elements on the list | |
protected DLLNode<E> head; // first node on the list, always null element, has next element but no prev | |
protected DLLNode<E> tail; // last node on the list, always null element, has prev element but no next | |
public DLinkedList(){ | |
head = new DLLNode<E>(null); | |
tail = new DLLNode<E>(null); | |
head.setNext(tail); | |
tail.setPrev(head); | |
numElements = 0; | |
} | |
// Returns the number of elements on the list | |
public int size() { | |
return numElements; | |
} | |
// Returns true if list is empty | |
public boolean isEmpty() { | |
return size() == 0; | |
} | |
// returns the position of the first element of list | |
// precondition: list is not empty | |
public DLLNode<E> first() { | |
return head.getNext(); | |
} | |
// returns the position of the last element of list or execute an exception if empty | |
// precondition: list is not empty | |
public DLLNode<E> last() { | |
return tail.getPrev(); | |
} | |
// returns the boolean value indicating if the given node is first one in the list | |
public boolean isFirst (DLLNode<E> node) { | |
return (node == first()); | |
} | |
// returns the boolean value indicating if the given node is last one in the list | |
public boolean isLast (DLLNode<E> node) { | |
return (node == last()); | |
} | |
// returns the position of the preceding node to the one at position or exception | |
public DLLNode<E> before (DLLNode<E> node) { | |
if (node == first()) | |
System.out.println("It is first node"); | |
return (node.getPrev()); | |
} | |
// returns the position of the following node to the one at position or exception | |
public DLLNode<E> after (DLLNode<E> node) { | |
if (node == first()) | |
System.out.println("It is last node"); | |
return (node.getNext()); | |
} | |
// replace element at position p with e, returning the old element at position p | |
public E replaceElement (DLLNode<E> node, E element) { | |
E temp = node.getInfo(); | |
node.setInfo(element); | |
return temp; | |
} | |
// swap the element stored at nodeA with nodeB | |
public void swapElements (DLLNode<E> nodeA, DLLNode<E> nodeB) { | |
E temp = nodeA.getInfo(); | |
nodeA.setInfo(nodeB.getInfo()); | |
nodeB.setInfo(temp); | |
} | |
// inserting an element in front of the list | |
public void insertFirst (E element) { | |
insertBefore(first(),element); | |
} | |
// inserting an element in the tail of the list | |
public void insertLast (E element) { | |
insertAfter(last(),element); | |
} | |
// inserts a new element in list before the node specified as argument | |
public DLLNode<E> insertBefore(DLLNode<E> node, E element) { | |
DLLNode<E> newNode = new DLLNode<E>(element); | |
// if list is empty or want to add before the first node | |
if ((isEmpty()) || (node == first())) { | |
newNode.setNext(head.getNext()); | |
newNode.setPrev(head); | |
head.getNext().setPrev(newNode); | |
head.setNext(newNode); | |
} | |
else { | |
newNode.setPrev(node.getPrev()); | |
newNode.setNext(node); | |
node.getPrev().setNext(newNode); | |
node.setPrev(newNode); | |
} | |
numElements++; | |
return newNode; | |
} | |
// inserts a new element in list after the node specified as argument | |
public DLLNode<E> insertAfter(DLLNode<E> node, E element) { | |
DLLNode<E> newNode = new DLLNode<E>(element); | |
// if list is empty or want to add after the last node | |
if ((isEmpty()) || (node == last())) { | |
newNode.setNext(tail); | |
newNode.setPrev(tail.getPrev()); | |
tail.getPrev().setNext(newNode); | |
tail.setPrev(newNode); | |
} | |
else { | |
newNode.setPrev(node); | |
newNode.setNext(node.getNext()); | |
node.getNext().setPrev(newNode); | |
node.setNext(newNode); | |
} | |
numElements++; | |
return newNode; | |
} | |
// removes an element e stored after the node specified as argument and returns the removed element | |
// precondition: argument node must not be last node of the list | |
public E removeAfter(DLLNode<E> node) { | |
return remove(node.getNext()); | |
} | |
// removes a node from the list and returns the removed element | |
public E remove(DLLNode<E> node) { | |
E temp = node.getInfo(); | |
node.getPrev().setNext(node.getNext()); | |
node.getNext().setPrev(node.getPrev()); | |
numElements--; | |
return temp; | |
} | |
public void print() { | |
DLLNode<E> temp = head.getNext(); | |
while (temp.getNext() != null) { | |
System.out.print(temp.getInfo() + " "); | |
temp = temp.getNext(); | |
} | |
} | |
private class DLLNode<E> { | |
private DLLNode<E> next; | |
private DLLNode<E> prev; | |
private E info; | |
// define constructor | |
public DLLNode(E info) { | |
this.next = null; | |
this.prev = null; | |
this.info = info; | |
} | |
// sets info of this DLLNode. | |
public void setInfo(E info) { | |
this.info = info; | |
} | |
// returns info of this DLLNode. | |
public E getInfo() { | |
return info; | |
} | |
// sets link of the next DLLNode. | |
public void setNext(DLLNode<E> next) { | |
this.next = next; | |
} | |
// returns link of next DLLNode. | |
public DLLNode<E> getNext() { | |
return next; | |
} | |
// sets link of previous DLLNode. | |
public void setPrev(DLLNode<E> prev) { | |
this.prev = prev; | |
} | |
// returns link of previous DLLNode. | |
public DLLNode<E> getPrev() { | |
return prev; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment