trypots.nethomeA Singly Linked List data structure
This is an implementation of a Singly Linked List. My aim here was to create a version of a singly linked list that would lend itself to students for use in testing this structure by emphasizing simplicity and the ability to easily create millions of records. The Node constructor therefore can automatically create integer values for every Node. The class has a variety of methods so that you can convert it to a queue or perhaps a stack structure easily. A truly simple linked list would only need a small subset of the methods provided here - in many cases, I just use the add method and fetch method.
This Singly Linked List uses a list header, which is perhaps more common in C where the list header would be a pointer. For an example of a Singly Linked List without a head, see Singly Linked List - Bag.
Singly Linked List:
public class SinglyLinkedList
{
private Node head;
private int count;
/**
* constructor
*/
public SinglyLinkedList() {
/**
* Creates a head node - this node is maintained as a reference to
* the first node and never itself holds any actual node data
* (users shouldn't know or care about this, however). Conceptually
* the head node is a pointer to the first node and is not itself
* a node. But since Java doesn't have pointers, the head node is
* in practice also a member of class Node. It should be referred
* to as the head, never as a Node, and certainly never as the first
* Node. It is not part of the count of nodes in the linked list.
*/
head = new Node(0, 0);
}
/**
* returns true if linked list is empty, false otherwise
*/
public boolean isEmpty(){
return (head.next == null);
}
/**
* insert a node at beginning of the linked list (this function could
* be used to implement a linked list as a stack)
*/
public void insert(Node node) {
node.next = head.next;
head.next = node;
++count;
}
/**
* insert a node at the end of the linked list (this function could be
* used to implement a linked list as a queue - in that case, also consider
* adding a tail pointer to the list data structure to improve the
* efficiency of insertions).
*/
public void insertLast(Node node) {
Node p = head;
while(p.next != null) {
p = p.next;
}
p.next = node;
++count;
}
/**
* removes and returns the first node from the linked list (this could
* be used to implement a linked list as a stack)
*/
public Node remove() {
Node p;
if((p = head.next) == null) {
return null;
}
else {
head.next = p.next;
}
--count;
return p;
}
/**
* removes and returns the last node from the linked list
*/
public Node removeLast() {
Node p = head.next;
Node q = head;
//empty list
if((p = head.next) == null) {
return p;
}
//traverse to end and remove last node
else {
while(p.next != null) {
q = p;
p = p.next;
}
--count;
q.next = null;
return p;
}
}
/**
* remove and returns a node by its value
*/
public Node remove(int lookFor) {
Node p = head.next;
Node q = head;
while(p != null && lookFor != p.value) {
q = p;
p = p.next;
}
if(p != null) {
q.next = p.next;
--count;
}
return p;
}
/**
* returns a node by its key value without removing it from the linked list
*/
public Node fetch(int lookFor) {
Node p = head.next;
Node q = head;
while(p != null && lookFor != p.value) {
q = p;
p = p.next;
}
return p;
}
public int size() {
return count;
}
public String toString() {
/* a simple string representation that includes the size of the
* list and it's first and last node values.
*/
if(!isEmpty()) {
Node current = head.next;
String result = "";
result += "List size = " + count + " / ";
result += "First node value = " + current.value + " / ";
while(current.next != null) {
current = current.next;
//System.out.println("" + current.value);
}
result += " Last node value = " + current.value;
return result;
}
else {
return "List is empty.";
}
}
}
A Node object:
public class Node {
private static int AutoNumberID;
//if you prefer, make these fields private and use setter/getter methods
public Node next;
public int value;
public Node() {
//generate a node with a random key and empty value
value = ++AutoNumberID;
}
public Node(int key, int value) {
//note: No real guarantee of unique keys although we do imitate the
// use of an ID generator with our autonumber field.
next = null;
this.value = value;
}
public String toString() {
return "" + this.value;
}
}
Demonstration:
public class SinglyLinkedList_Tests {
public static void main(String[] args) {
int NUM_NODES = 1000000;
long startTime = System.currentTimeMillis();
long timeElapsed = 0;
SinglyLinkedList list = new SinglyLinkedList();
for(int i = 0; i < NUM_NODES; ++i)
list.insert(new Node());
timeElapsed = System.currentTimeMillis() - startTime;
System.out.print("[timeElapsed: " + timeElapsed + "ms]");
System.out.println(" Inserted " + NUM_NODES + " nodes");
//remove first
timeElapsed = System.currentTimeMillis() - startTime;
System.out.print("[timeElapsed: " + timeElapsed + "ms]");
System.out.println(" removed first node [" + list.remove() + "]");
//remove middle
timeElapsed = System.currentTimeMillis() - startTime;
System.out.print("[timeElapsed: " + timeElapsed + "ms]");
System.out.println(" removed middle node [" + list.remove(NUM_NODES / 4) + "]");
//remove middle
timeElapsed = System.currentTimeMillis() - startTime;
System.out.print("[timeElapsed: " + timeElapsed + "ms]");
System.out.println(" removed middle node [" + list.remove(NUM_NODES / 2) + "]");
//remove middle
timeElapsed = System.currentTimeMillis() - startTime;
System.out.print("[timeElapsed: " + timeElapsed + "ms]");
System.out.println(" removed middle node [" + list.remove(NUM_NODES / 4 * 3) + "]");
//remove last (requires a full traversal of list
timeElapsed = System.currentTimeMillis() - startTime;
System.out.print("[timeElapsed: " + timeElapsed + "ms]");
System.out.println(" removed last node [" + list.removeLast() + "]");
}
}