Last active
December 20, 2015 19:59
-
-
Save petehuang/6187258 to your computer and use it in GitHub Desktop.
Singly linked list implementation in Java
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 ListNode { | |
//has two pieces: data and pointer to next node | |
private int value; | |
private ListNode next; | |
//constructors | |
public ListNode() { | |
} | |
public ListNode(int value) { | |
this.value = value; | |
} | |
public ListNode(int value, ListNode next) { | |
this.value = value; | |
this.next = next; | |
} | |
//since data and next are private, we have to have getters and setters | |
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; | |
} | |
} | |
//now that we have the list node, we need to construct the list | |
//the list should have a root, a current size, and a maximum size | |
//we should be able to set the root of the list and get the current/max sizes | |
//we should be able to insert after a certain node as well as at the beginning | |
//we should be able to remove both the nth node as well as a value in the list | |
private ListNode root; | |
private int number; | |
private int maximum = 15; | |
public class List { | |
public void setRoot(ListNode root) { | |
root.next = this.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 = this.root; | |
ListNode tmp2 = new ListNode(value); | |
//check for size | |
if (this.number == this.maximum) { | |
return "The list is full." | |
} | |
//check for empty list | |
if (this.root == null) { | |
this.root = tmp2; | |
} | |
//keep getting next until you hit the end, then add the node | |
while (tmp.getNext() != null) { | |
tmp = tmp.getNext(); | |
} | |
tmp.setNext(tmp); | |
this.number++; | |
} | |
public void insert_at_nth(int n, int value) { | |
int count = 0; | |
ListNode tmp2 = new ListNode(value); | |
ListNode tmp = this.root; | |
//again, check for size and empty list | |
if (this.number == this.maximum) { | |
return "The list is full." | |
} | |
if (this.root == null) { | |
this.root = tmp2; | |
} | |
while (count < n) { | |
tmp = tmp.getNext(); | |
count++; | |
} | |
//tmp is now the nth node | |
//new node's next is the old next | |
tmp2.setNext(tmp.getNext()); | |
//point old node's next to new node | |
tmp.setNext(tmp2); | |
this.number++; | |
} | |
public void remove_nth(unsigned int n) { | |
ListNode tmp = this.root; | |
//check for empty list | |
if (this.root == null) { | |
return; | |
} | |
//if asking to remove 0th node, make the next NODE the root | |
if (n == 0) { | |
this.root = this.root.getNext(); | |
} | |
//navigate to (n-1)th node | |
for (int i = 0; i < n-1; i++) { | |
tmp = tmp.getNext(); | |
} | |
tmp.setNext(tmp.getNext().getNext()); | |
this.number--; | |
} | |
public void remove_value(int value) { | |
ListNode tmp = this.root; | |
if(this.root == null) { | |
return; | |
} | |
if(tmp.value == value) { | |
this.root = this.root.getNext(); | |
} | |
while(tmp.getNext().getValue() != value) { | |
tmp = tmp.getNext(); | |
if(tmp.getNext() == null) { | |
return; | |
} | |
} | |
tmp.setNext(tmp.getNext().getNext()); | |
} | |
} | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment