Skip to content

Instantly share code, notes, and snippets.

@ru-rocker
Last active May 29, 2017 08:17
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save ru-rocker/949a227e4bcc72995be763ba763e1459 to your computer and use it in GitHub Desktop.
Save ru-rocker/949a227e4bcc72995be763ba763e1459 to your computer and use it in GitHub Desktop.
Implementation of DoublyLinkedList algorithm
package com.rurocker.algo.ds;
/**
* DoublyLinkedList implementation
* Created by ricky on 5/29/17.
*/
public class DoublyLinkedList<E> {
private int size;
private Node<E> head;
private Node<E> tail;
public DoublyLinkedList() {
size = 0;
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public Node insertHead(E element) {
Node tmp = new Node(element, head, null);
if (head != null) {
head.prev = tmp;
}
head = tmp;
if (tail == null) {
tail = tmp;
}
size++;
return tmp;
}
public Node insertTail(E element) {
Node tmp = new Node(element, null, tail);
if (tail != null) {
tail.next = tmp;
}
tail = tmp;
if (head == null) {
head = tmp;
}
size++;
return tmp;
}
public Node insertAfter(E element, Node prevNode) {
if(size == 0){
throw new IllegalStateException("List is empty");
}
if(prevNode == tail){
return insertHead(element);
}
Node tmp = new Node(element, prevNode.next, prevNode);
prevNode.next.prev = tmp;
prevNode.next = tmp;
size++;
return tmp;
}
public void removeHead() {
if (size == 0) {
throw new IllegalStateException("List is empty");
}
head = head.next;
size--;
}
public void removeTail() {
if (size == 0) {
throw new IllegalStateException("List is empty");
}
if (size == 1) {
removeHead();
} else {
tail = tail.prev;
tail.next = null;
size--;
}
}
public void remove(Node<E> node){
Node temp = head;
while(temp != null){
if(temp == node){
Node prev = temp.prev;
Node next = temp.next;
temp.prev.next = next;
temp.next.prev = prev;
size--;
break;
}
temp = temp.next;
}
}
public void print() {
Node temp = head;
System.out.print("Doubly Linked List: ");
while (temp != null) {
System.out.print(" " + temp.element);
temp = temp.next;
}
System.out.println();
}
public static void main(String[] args) {
DoublyLinkedList<Integer> dll = new DoublyLinkedList<>();
dll.insertHead(10);
dll.insertHead(20);
dll.insertHead(30);
dll.insertTail(40);
Node n = dll.insertTail(50);
dll.insertTail(60);
dll.insertAfter(55,n);
dll.print();
dll.removeHead();
dll.print();
dll.removeTail();
dll.print();
dll.remove(n);
dll.print();
}
}
class Node<E> {
E element;
Node<E> next;
Node<E> prev;
public Node(E element, Node next, Node prev) {
this.element = element;
this.next = next;
this.prev = prev;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment