Linked Lists in Java

Linked lists are one of the most fundamental data structures used in computer science and are essential to the understanding of many other data structures. In this article, we will be discussing what linked lists are, how they are implemented using classes in Java, their types, and how to traverse, insert, and delete elements from them. We will also be discussing skip lists and their applications. By the end of this article, you should have a comprehensive understanding of linked lists and their applications.

Overview of Linked Lists

Linked lists are linear data structures that consist of a sequence of items, each item being linked to the next. Linked lists are dynamic data structures, meaning that their size can be adjusted at run-time. Unlike arrays, linked lists do not have a fixed size and can grow and shrink as needed. Linked lists are also flexible, meaning that items can be added and removed from any position in the list.

There are two types of linked lists: singly linked lists and doubly linked lists. Singly linked lists contain only the next link and doubly linked lists contain both the next and previous links.

Implementing Linked Lists Using Classes

In Java, linked lists can be implemented using classes. A Node class can be used to represent each item in the list and will contain a reference to the next item in the list. The list itself can be implemented using a List class, which consists of a reference to the head of the list, the tail of the list, and methods for adding and removing items.

public class Node { 
	int data; 
	Node next; 

	public Node(int data) { 
		this.data = data; 
		this.next = null; 
	} 
}

public class List { 
	Node head; 
	Node tail; 

	public List() { 
		head = null; 
		tail = null; 
	} 

	public void add(int data) { 
		Node newNode = new Node(data); 
		if (head == null) { 
			head = newNode; 
			tail = newNode; 
		} else { 
			tail.next = newNode; 
			tail = newNode; 
		} 
	} 
}

Singly Linked Lists

Singly linked lists are linear data structures that consist of a sequence of items, each item being linked to the next. In a singly linked list, each item contains a reference to the next item in the list. The last item in the list contains a reference to null, indicating the end of the list.

public class SinglyLinkedList { 
	Node head; 

	public SinglyLinkedList() { 
		head = null; 
	} 

	public void add(int data) { 
		Node newNode = new Node(data); 
		if (head == null) { 
			head = newNode; 
		} else { 
			Node current = head; 
			while (current.next != null) { 
				current = current.next; 
			} 
		current.next = newNode; 
		} 
	} 
}

Doubly Linked Lists

Doubly linked lists are linear data structures that consist of a sequence of items, each item being linked to both the next and previous items. In a doubly linked list, each item contains a reference to the next and previous items in the list. The first item in the list contains a reference to null, indicating the start of the list. The last item in the list contains a reference to null, indicating the end of the list.

public class DoublyLinkedList { 
	Node head; 
	Node tail; 

	public DoublyLinkedList() { 
		head = null; 
		tail = null; 
	} 

	public void add(int data) { 
		Node newNode = new Node(data); 
		if (head == null) { 
			head = newNode; 
			tail = newNode; 
		} else { 
			tail.next = newNode; 
			newNode.previous = tail; 
			tail = newNode; 
		} 
	} 
}

Traversing Linked Lists

Linked lists can be traversed in two ways: iteratively and recursively. Iterative traversal involves looping through the list until the desired item is found. Recursive traversal involves using a recursive function to traverse the list until the desired item is found.

// Iterative
public void traverse(Node node) { 
	while (node != null) { 
		System.out.println(node.data); 
		node = node.next; 
	} 
}

// Recursive
public void traverse(Node node) { 
	if (node == null) 
		return; 
	System.out.println(node.data); 
	traverse(node.next); 
}

Inserting and Deleting Elements from Linked Lists

Elements can be inserted and deleted from linked lists in various ways. To insert an element, you can use either the add() or insert() methods. To delete an element, you can use either the remove() or delete() methods.

// Insert 
public void insert(int index, int data) { 
	Node node = new Node(data); 
	if (index == 0) { 
		node.next = head; 
		head = node; 
	} else { 
		Node current = head; 
		int i = 0; 
		while (i < index - 1) { 
			current = current.next; 
			i++; 
		} 
		node.next = current.next; 
		current.next = node; 
	} 
} 

// Delete 
public void delete(int index) { 
	if (index == 0) 
		head = head.next; 
	else { 
		Node current = head; 
		int i = 0; 
		while (i < index - 1) { 
			current = current.next; 
			i++; 
		} 
	current.next = current.next.next; 
	} 
}

Skip Lists

Skip lists are a type of linked list that allows for fast search and insertion operations. Skip lists are composed of multiple levels, with each level containing a subset of the elements in the list. The top level contains all of the elements, while the lower levels contain increasingly fewer elements. This structure allows for fast search and insertion operations, as the desired element can be found by starting at the top level and working down.

public class SkipList { 
	Node head; 
	Node tail; 
	int levels; 

	public SkipList() { 
		head = null; 
		tail = null; 
		levels = 0; 
	} 

	public void add(int data) { 
		Node newNode = new Node(data); 
		if (head == null) { 
			head = newNode; 
			tail = newNode; 
			levels = 1; 
		} else { 
			tail.next = newNode; 
			tail = newNode; 
			levels++; 
		} 
	} 
}

Conclusion

In this article, we have discussed linked lists, their types, how to implement them using classes in Java, how to traverse them, and how to insert and delete elements from them. We have also discussed skip lists and their applications. By the end of this article, you should have a comprehensive understanding of linked lists and their applications.

Exercises

// Iterative
public void traverseList(Node head) { 
	Node current = head; 
	while (current != null) { 
		System.out.println(current.data); 
		current = current.next; 
	} 
}

// Recursive 
public void traverseList(Node head) { 
	if (head == null) 
		return; 
	System.out.println(head.data); 
	traverseList(head.next); 
}

public void insertAtEnd(int data) { 
	Node newNode = new Node(data); 
	if (head == null) { 
		head = newNode; 
		tail = newNode; 
	} else { 
		tail.next = newNode; 
		newNode.previous = tail; 
		tail = newNode; 
	} 
} 

public void deleteNode(Node head, int data) { 
	Node current = head; 
	if (current.data == data) { 
		head = current.next; 
		return; 
	} 
	while (current.next != null) { 
		if (current.next.data == data) { 
			current.next = current.next.next; 
			return; 
		} 
		current = current.next; 
	} 
}

public Node search(int data) { 
	Node current = head; 
	int level = levels - 1; 
	while (level >= 0) { 
		while (current.next != null && current.data < data) { 
			current = current.next; 
			} 
		if (current.data == data) 
			return current; 
		level--; 
		current = current.down; 
	} 
	return null; 
}

public void deleteNode(int data) { 
	Node current = head; 
	while (current != null) { 
		if (current.data == data) { 
			if (current == head) { 
				head = current.next; 
				head.previous = null; 
				return; 
			} 
			if (current == tail) { 
				tail = current.previous; 
				tail.next = null; 
				return; 
			} 
			current.previous.next = current.next; 
			current.next.previous = current.previous; 
			return; 
		} 
	current = current.next; 
	} 
}