Java Concepts: Linked List Lab
Linked lists are basic data structures in programming. Almost every programming language has some sort of linked list implemented as a library, as well as many ways to construct linked lists. Java is no exception. And while Java can implement a linked list, it helps for programmers to know how linked lists work, and what they do. That way, programmers can understand how to tweak them for certain situations or optimize them for certain systems.
Other People Are Reading
-
Nodes
-
Every linked list has as its component part a "node," which contains both the data being stored and a variable that references the next item in the list. Some more complex lists contain nodes that reference multiple other nodes, but for the basic list, the reference only points to the next node in the list. The data stored in the list can be of any kind.
Linked List Class
-
In Java, a linked list will contain, at minimum, two classes: the main list class, and a node class. The following example illustrates this difference. In this list, the node class resides as a private member of the list class, so that only the list can manipulate nodes. In order for a user to add or remove elements, she must go through the class interface:
public class LList{private static class Node{
int data;
Node next;
}}
-
Inserting Into the List
-
Each list will have an insertion method. This method will take a user value, in this case an integer, and insert a node containing that value along the list. This also means that each list will contain a simple variable that will represent a head node, so that the list knows when it is empty or when the user is at the start of the list:
Node head = null;public void insertNode(int value){
Node temp = new Node();
new.data = value;if(head == null){
head = temp;
temp.next = null;
}else{
Node current = head;while(current.next != null){
current == current.next;
}current.next = temp;
temp.next = null;
}
Removing From the List
-
Removing from the list is a little more complicated. In a simple list, the user will only add onto the end of the list. With removal, she may remove a node from the middle. In this case, the programmer must ensure that the list stays coherent by making sure the node previous to the removed node refers to the node after the removed node:
public void removeNode(int value){if (head != null){
Node current = head.next;
Node trail = head;while (current != null && current.data != value){
trail = current;
current = current.next;
}if(current.data == value){
trail.next = current.next;
current = null;
return;
}
else if(current == null){
System.out.println("Element not in List");
return;
}
}
}
-
