Skip to content

Instantly share code, notes, and snippets.

@arrayed
Created December 30, 2016 18:20
Show Gist options
  • Save arrayed/c2ad7933c0fcc1990d07fd445eac799f to your computer and use it in GitHub Desktop.
Save arrayed/c2ad7933c0fcc1990d07fd445eac799f to your computer and use it in GitHub Desktop.
Linked List Base List Implementation in Java
//============================================================================
// 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