Created
November 14, 2019 18:53
-
-
Save quinnzipse/bab888cf7d80153f621a9179daa66084 to your computer and use it in GitHub Desktop.
A simple doubly linked list with some added methods enclosed in a private inner class.
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
public class DoublyLinkedList { | |
private int size; | |
private NumberNode head; | |
private NumberNode tail; | |
public DoublyLinkedList() { | |
clear(); | |
} | |
public void clear() { | |
head = new NumberNode(0, null, null); | |
tail = new NumberNode(0, null, null); | |
size = 0; | |
} | |
public void add(int value) { | |
add(value, size); | |
} | |
public void remove(int where) { | |
// Check for a valid index | |
if (where > size - 1 || where < 0) { | |
throw new IndexOutOfBoundsException(); | |
} | |
// Get the nodes before and after. | |
NumberNode before = getNodeBefore(where), | |
after = before.getNext().getNext(); | |
// Set the pointers to skip the middle | |
before.setNext(after); | |
after.setPrev(before); | |
// Decrease the size. | |
size--; | |
} | |
public NumberNode getNodeBefore(int pos) { | |
NumberNode result; | |
if (pos < size / 2) { | |
result = head; | |
for (int i = 0; i < pos; i++) { | |
result = result.getNext(); | |
} | |
} else { | |
result = tail; | |
for (int i = size + 1; i > pos; i--) { | |
result = result.getPrev(); | |
} | |
} | |
return result; | |
} | |
/** | |
* This creates a whole new array with less elements without effecting the old list. | |
* | |
* @param n number of elements to drop | |
* @return the new list. | |
*/ | |
public NumberList drop(int n) { | |
// Check for valid input | |
if (n < 0 || n > size) throw new IndexOutOfBoundsException(); | |
// Setup result list | |
final NumberList result = new NumberList(); | |
NumberNode node = head.getNext(); | |
int index = 0, maxIndex = size - n; | |
while (index < maxIndex) { | |
result.add(node.getNum(), index); | |
index++; | |
node = node.getNext(); | |
} | |
// Cleanup work/finishing steps here | |
return result; | |
} | |
public void add(int value, int where) { | |
// Check for a valid index | |
if (where > size || where < 0) { | |
throw new IndexOutOfBoundsException(); | |
} | |
// Now look at the node before | |
NumberNode before = getNodeBefore(where), | |
after = before.getNext(), | |
newNode = new NumberNode(value, before, after); | |
// Tell the nodes about the new node. | |
before.setNext(newNode); | |
after.setPrev(newNode); | |
// Increment the size. | |
size++; | |
} | |
private NumberNode getNode(int index) { | |
// Check for OB error | |
if (index > size - 1 || index < 0) throw new IndexOutOfBoundsException(); | |
NumberNode result; | |
if (index < size / 2) { | |
// traverse from the front | |
result = head; | |
for(int i=0; i<index; i++){ | |
result = head.getNext(); | |
} | |
} else { | |
// traverse from the back of the list. | |
result = tail; | |
for(int i=size; i>index; i--){ | |
result = head.getPrev(); | |
} | |
} | |
return result; | |
} | |
private class NumberNode { | |
private int num; | |
private NumberNode next; | |
private NumberNode prev; | |
private NumberNode(int num, NumberNode prev, NumberNode next) { | |
this.num = num; | |
this.next = next; | |
this.prev = prev; | |
} | |
private NumberNode getNext() { | |
return next; | |
} | |
private void setNext(NumberNode next) { | |
this.next = next; | |
} | |
private NumberNode getPrev() { | |
return prev; | |
} | |
private void setPrev(NumberNode prev) { | |
this.prev = prev; | |
} | |
private int getNum() { | |
return this.num; | |
} | |
} | |
public static void main(String[] args) { | |
NumberList list = new NumberList(); | |
list.add(10, 0); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment