The Singly Linked List

In a singly linked list each node only has a single link to another (next) node. To store a single linked list, you only need to store a reference or pointer to the first node in that list. The last node has a pointer to NULL to indicate that it is the last node.

To define a singly linked list element create a separate class where each element will be an instance of this class. The class will have two property variables: data itself, and a pointer to the next node. Create another class where the list itself will be instantiated as an object. This class will define all methods that the list utilizes, such as insertFirst(), insertLast(), deleteFirst(), deleteLast(), and printList().

The following is a Java code that uses static inner classes:

package dsmy.linkedlist;

public class App {

	public static void main(String[] args) {
		SinglyLinkedList list = new SinglyLinkedList();
		list.insertFirst("First String");
		list.insertFirst("Second String");
		list.insertFirst("Third String");
		list.insertLast("Last String");
		list.deleteFirst();
		list.deleteLast();
		list.printList();

	}
	
	static class SinglyLinkedList {
		private Node first;
		
		public void insertFirst(Object data) {
			Node node = new Node(data);
			node.next = this.first;
			first = node;
		}
		
		public void insertLast(Object data) {
			// Traverse the list from beginning to the last node
			Node current = first;
			while (current.next != null) {
				current = current.next;
			}
			// Insert the node
			Node node = new Node(data);
			current.next = node;			
		}
		
		public void deleteFirst() {
			// The following node becomes the first one
			first = first.next;			
		}
		
		public void deleteLast() {
			// Traverse the list from beginning to one before 
                        // the last node
			Node current = first;
			while (current.next.next != null) {
				current = current.next;
			}
			// The node before the last one becomes the last
			current.next = null;
		}
		
		public void printList() {
			System.out.println("First --> Last");
			Node current = first;
			while (current != null) {
				current.displayNode();
				current = current.next;
			}
		}
	}
	
	static class Node {
		private Object data;
		private Node next;
		
		Node(Object data) {
			this.data = data;
		}
		
		public void displayNode() {
			System.out.print("{ " + data + " } \t");
		}		
	}
}