Last active
May 29, 2017 08:17
-
-
Save ru-rocker/949a227e4bcc72995be763ba763e1459 to your computer and use it in GitHub Desktop.
Implementation of DoublyLinkedList algorithm
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 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