Skip to content

Instantly share code, notes, and snippets.

@quinnzipse
Created November 14, 2019 18:53
Show Gist options
  • Save quinnzipse/bab888cf7d80153f621a9179daa66084 to your computer and use it in GitHub Desktop.
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.
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