Skip to content

Instantly share code, notes, and snippets.

@petehuang
Last active December 20, 2015 19:59
Show Gist options
  • Save petehuang/6187258 to your computer and use it in GitHub Desktop.
Save petehuang/6187258 to your computer and use it in GitHub Desktop.
Singly linked list implementation in Java
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