Skip to content

Instantly share code, notes, and snippets.

@petehuang
Last active December 20, 2015 20:09
Show Gist options
  • Save petehuang/6188525 to your computer and use it in GitHub Desktop.
Save petehuang/6188525 to your computer and use it in GitHub Desktop.
Doubly Linked List implementation in Java, missing "remove value" method
//same ListNode as SLL except with prev, getPrevious, setPrevious
public class ListNode {
private int value;
private ListNode prev;
private ListNode next;
//need constructor, get/set values/prev/next
public ListNode() {
}
public ListNode(int value) {
this.value = value;
}
public ListNode(int value, ListNode next) {
this.value = value;
this.next = next;
}
public ListNode(int value, ListNode next, ListNode prev) {
this.value = value;
this.next = next;
this.prev = prev;
}
public int getValue() {
return this.value;
}
public void setValue(int value) {
this.value = value;
}
public ListNode getNext() {
return this.next;
}
public void setNext(ListNode next) {
this.next = next;
}
public ListNode getPrev() {
return this.prev;
}
public void setPrev(ListNode prev) {
this.prev = prev;
}
}
//has root, tail, current size called number, max size called maximum
//getSize, getMax, setRoot, insert at end, insert at n, remove nth, remove value
private ListNode root;
private ListNode tail;
private int number;
private int maximum = 15;
public class List {
public void setRoot(ListNode root) {
this.root = root;
}
public int getSize() {
return this.number;
}
public int getMax() {
return this.maximum;
}
public void insert_at_end(int value) {
ListNode tmp = new ListNode(value);
ListNode tmp2 = this.tail;
if (number == maximum) {
return "Sorry, this list is full.";
}
if (this.root == null) {
this.root = tmp;
}
tmp.setPrev(tmp2);
tmp2.setNext(tmp);
this.setTail(tmp);
this.number++;
}
public void insert_at_nth(int value, int n) {
ListNode tmp = new ListNode(value);
ListNode tmp2 = this.root;
if (number == maximum) {
return "Sorry, this list is full.";
}
if (n == 0) {
tmp2.setPrev(tmp);
tmp.setNext(tmp);
this.setRoot(tmp);
}
if (this.root == null) {
this.setRoot(tmp);
}
for (int i = 0; i < n; i++) {
while (tmp2.getNext() != null) {
tmp2 = tmp2.getNext();
}
}
tmp.setPrev(tmp2);
tmp.setNext(tmp2.getNext());
tmp2.setNext(tmp);
tmp2.getNext().setPrev(tmp);
number++;
}
public void remove_at_nth(unsigned int n) {
ListNode tmp = this.root;
if (this.root == null) {
return;
}
if (n == 0) {
tmp.getNext().setPrev() = null;
this.setRoot(tmp.getNext());
}
for (int i = 0; i < n; i++) { //navigate to n
while (tmp.getNext() != null) {
tmp = tmp.getNext();
}
}
tmp.getPrev().setNext(tmp.getNext());
tmp.getNext().setPrev(tmp.getPrev());
number--;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment