Lists
Lists are a abstract data type, they are a ordered collection, there are many classes that implement the List interface as seen below.
I have already covered lists in depth in my Java Reference Section, below I will cover some of the more complex List examples.
First I will take a look at ArrayList which is commonly used in Java, ArrayList have been around since JDK 1.2, ArrayList is NOT synchronized, thus you get better performance if you application does not need synchronization.
| Employee Class (used by many examples below) | package uk.co.datadisk.linkedlist;
import java.util.Objects;
public class Employee {
private String firstName;
private String lastName;
private int id;
public Employee(String firstName, String lastName, int id) {
this.firstName = firstName;
this.lastName = lastName;
this.id = id;
}
public String getFirstName() {
return firstName;
}
public void setFirstName(String firstName) {
this.firstName = firstName;
}
public String getLastName() {
return lastName;
}
public void setLastName(String lastName) {
this.lastName = lastName;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
@Override
public String toString() {
return "Employee{" +
"firstName='" + firstName + '\'' +
", lastName='" + lastName + '\'' +
", id=" + id +
'}';
}
// comparing employee id, firstName and lastName
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Employee employee = (Employee) o;
return id == employee.id &&
Objects.equals(firstName, employee.firstName) &&
Objects.equals(lastName, employee.lastName);
}
// using id, firstName and lastName for hashCode
@Override
public int hashCode() {
return Objects.hash(firstName, lastName, id);
}
} |
| ArrayList example | package uk.co.datadisk.linkedlist;
import java.util.ArrayList;
import java.util.List;
public class Main_ArrayLists {
public static void main(String[] args) {
List<Employee> employeeList = new ArrayList<>();
Employee paul = new Employee("Paul", "Valle", 1000);
employeeList.add(paul);
employeeList.add(new Employee("Lorraine", "Valle", 1001));
employeeList.add(new Employee("Dominic", "Valle", 1002));
employeeList.add(new Employee("Jessica", "Valle", 1003));
employeeList.forEach(employee -> System.out.println(employee)); // use lambda
System.out.println(employeeList.get(1));
System.out.println("Empty List? " + employeeList.isEmpty());
employeeList.set(2, new Employee("Will", "Hay", 1004));
employeeList.forEach(employee -> System.out.println(employee));
System.out.println("Employee linkedlist size: " + employeeList.size()); // size of List not capacity of List
employeeList.add(2, new Employee("Dominic", "Valle", 1002));
employeeList.forEach(employee -> System.out.println(employee));
Employee[] employeeArray = employeeList.toArray(new Employee[employeeList.size()]);
for(Employee employee: employeeArray){
System.out.println(employee);
}
System.out.println("Contains Employee? " + employeeList.contains(new Employee("Paul", "Valle", 1000)));
System.out.println("Index of Lorraine: " + employeeList.indexOf(new Employee("Lorraine", "Valle", 1001)));
employeeList.remove(3);
employeeList.forEach(employee -> System.out.println(employee));
}
} |
Vectors is a thread safe ArrayList (synchronized), Vectors have been around since JDK 1.0, you can see that Vector methods are synchronized.
| Vector example | package uk.co.datadisk.linkedlist;
import java.util.List;
import java.util.Vector;
public class Main_Vector {
public static void main(String[] args) {
// VECTOR IS TREAD SAFE
List<Employee> employeeList = new Vector<>();
Employee paul = new Employee("Paul", "Valle", 1000);
employeeList.add(paul);
employeeList.add(new Employee("Lorraine", "Valle", 1001));
employeeList.add(new Employee("Dominic", "Valle", 1002));
employeeList.add(new Employee("Jessica", "Valle", 1003));
employeeList.forEach(employee -> System.out.println(employee));
System.out.println(employeeList.get(1));
System.out.println(employeeList.isEmpty());
employeeList.set(2, new Employee("Will", "Hay", 1004));
employeeList.forEach(employee -> System.out.println(employee));
System.out.println("Employee linkedlist size: " + employeeList.size());
employeeList.add(2, new Employee("Dominic", "Valle", 1002));
employeeList.forEach(employee -> System.out.println(employee));
Employee[] employeeArray = employeeList.toArray(new Employee[employeeList.size()]);
for(Employee employee: employeeArray){
System.out.println(employee);
}
System.out.println(employeeList.contains(new Employee("Paul", "Valle", 1000)));
System.out.println("Index of Lorraine: " + employeeList.indexOf(new Employee("Lorraine", "Valle", 1001)));
employeeList.remove(3);
employeeList.forEach(employee -> System.out.println(employee));
}
} |
You can have singly or double linked lists, each item in the list is called a node, the first item in the list is called the head node, the last item in the list will point to null.
The below example is of a singly linked list so that you can understand, you would normally use the JDK version.
| Employee Single Node | package uk.co.datadisk.linkedlist;
public class EmployeeSingleNode {
private Employee employee;
private EmployeeSingleNode next;
public EmployeeSingleNode(Employee employee) {
this.employee = employee;
}
public Employee getEmployee() {
return employee;
}
public void setEmployee(Employee employee) {
this.employee = employee;
}
public EmployeeSingleNode getNext() {
return next;
}
public void setNext(EmployeeSingleNode next) {
this.next = next;
}
@Override
public String toString() {
return employee.toString();
}
} |
| Employee Single LinkedList | package uk.co.datadisk.linkedlist;
public class EmployeeSingleLinkedList {
private EmployeeSingleNode head;
private int size;
public void addToFront(Employee employee){
EmployeeSingleNode node = new EmployeeSingleNode(employee);
node.setNext(head);
head = node;
size++;
}
public void printList(){
EmployeeSingleNode current = head;
System.out.print("HEAD -> ");
while(current != null){
System.out.println(current);
System.out.print(" -> ");
current = current.getNext();
}
System.out.println("null\n");
}
public int getSize() {
return size;
}
public boolean isEmpty(){
return head == null;
}
public EmployeeSingleNode removeFromFront() {
if(isEmpty()){
return null;
}
EmployeeSingleNode removedNode = head;
head = head.getNext();
size--;
removedNode.setNext(null);
return removedNode;
}
} |
| Main LinkedList | package uk.co.datadisk.linkedlist;
public class Main_Single_Linked_List {
public static void main(String[] args) {
Employee paul = new Employee("Paul", "Valle", 1000);
Employee lorraine = new Employee("Lorraine", "Valle", 1001);
Employee dominic = new Employee("Dominic", "Valle", 1002);
Employee jessica = new Employee("Jessica", "Valle", 1003);
EmployeeSingleLinkedList list = new EmployeeSingleLinkedList();
list.addToFront(paul);
list.addToFront(lorraine);
list.addToFront(dominic);
list.addToFront(jessica);
System.out.println("Is linked linkedlist empty: " + list.isEmpty());
System.out.println("Size of linked linkedlist: " + list.getSize());
list.printList();
list.removeFromFront();
list.printList();
}
} |
Now for a double linked list example, again you would use the JDK double linked list version.
| Employee Double Node | package uk.co.datadisk.linkedlist;
public class EmployeeDoubleNode {
private Employee employee;
private EmployeeDoubleNode next;
private EmployeeDoubleNode previous;
public EmployeeDoubleNode(Employee employee) {
this.employee = employee;
}
public Employee getEmployee() {
return employee;
}
public void setEmployee(Employee employee) {
this.employee = employee;
}
public EmployeeDoubleNode getPrevious() {
return previous;
}
public void setPrevious(EmployeeDoubleNode previous) {
this.previous = previous;
}
public EmployeeDoubleNode getNext() {
return next;
}
public void setNext(EmployeeDoubleNode next) {
this.next = next;
}
@Override
public String toString() {
return employee.toString();
}
} |
| Employee Double LinkedList | package uk.co.datadisk.linkedlist;
public class EmployeeDoubleLinkedList {
private EmployeeDoubleNode head;
private EmployeeDoubleNode tail;
private int size;
public void addToFront(Employee employee){
EmployeeDoubleNode node = new EmployeeDoubleNode(employee);
if(head == null){
tail = node;
} else {
head.setPrevious(node);
node.setNext(head);
}
head = node;
size++;
}
public void addToEnd(Employee employee){
EmployeeDoubleNode node = new EmployeeDoubleNode(employee);
if(tail == null){
head = node;
} else {
tail.setNext(node);
node.setPrevious(tail);
}
tail = node;
size++;
}
public void printList(){
EmployeeDoubleNode current = head;
System.out.print("HEAD -> ");
while(current != null){
System.out.println(current);
System.out.print(" <=> ");
current = current.getNext();
}
System.out.println("null\n");
}
public int getSize() {
return size;
}
public boolean isEmpty(){
return head == null;
}
public EmployeeDoubleNode removeFromFront() {
if(isEmpty()){
return null;
}
EmployeeDoubleNode removedNode = head;
if(head.getNext() == null){
tail = null;
} else {
head.getNext().setPrevious(null);
}
head = head.getNext();
size--;
removedNode.setNext(null);
return removedNode;
}
public EmployeeDoubleNode removeFromEnd() {
if(isEmpty()){
return null;
}
EmployeeDoubleNode removedNode = tail;
if( tail.getPrevious() == null){
head = null;
} else {
tail.getPrevious().setNext(null);
}
tail = tail.getPrevious();
size--;
removedNode.setPrevious(null);
return removedNode;
}
public boolean addBefore(Employee newEmployee, Employee existingEmployee){
if(head == null){
return false;
}
// find existing employee
EmployeeDoubleNode current = head;
while(current != null && !current.getEmployee().equals(existingEmployee)){
current = current.getNext();
}
if(current == null) {
return false;
}
EmployeeDoubleNode newNode = new EmployeeDoubleNode(newEmployee);
newNode.setPrevious(current.getPrevious());
newNode.setNext(current);
current.setPrevious(newNode);
if(head == current){
head = current;
} else {
newNode.getPrevious().setNext(newNode);
}
size++;
return true;
}
} |
| Main Double LinkedList | package uk.co.datadisk.linkedlist;
public class Main_Double_Linked_List {
public static void main(String[] args) {
Employee paul = new Employee("Paul", "Valle", 1000);
Employee lorraine = new Employee("Lorraine", "Valle", 1001);
Employee dominic = new Employee("Dominic", "Valle", 1002);
Employee jessica = new Employee("Jessica", "Valle", 1003);
EmployeeDoubleLinkedList list = new EmployeeDoubleLinkedList();
list.addToFront(paul);
list.addToFront(lorraine);
list.addToFront(dominic);
list.addToFront(jessica);
Employee graham = new Employee("Graham", "Moffitt", 1005);
list.addBefore(graham, dominic);
list.printList();
System.out.println("List size: " + list.getSize());
Employee will = new Employee("Will", "Hay", 1004);
list.addToEnd(will);
list.printList();
System.out.println("List size: " + list.getSize());
list.removeFromFront();
list.printList();
System.out.println("List size: " + list.getSize());
list.removeFromEnd();
list.printList();
System.out.println("List size: " + list.getSize());
}
} |
As mentioned the JDK has its own LinkedList (doubly linked list), its also not sychronized (look at BlockingQueue or ConcurrentLinkedDeque for alternatives, or create your own wwrapper to peek/pop methods, etc.), the JDK uses its own node implementation as seen below
Below is an example on how to use
| JDK LinkedList | package uk.co.datadisk.linkedlist;
import java.util.Iterator;
import java.util.LinkedList;
public class Main_JDK_LinkedList {
public static void main(String[] args) {
Employee paul = new Employee("Paul", "Valle", 1000);
Employee lorraine = new Employee("Lorraine", "Valle", 1001);
Employee dominic = new Employee("Dominic", "Valle", 1002);
Employee jessica = new Employee("Jessica", "Valle", 1003);
LinkedList<Employee> list = new LinkedList<>();
list.addFirst(paul);
list.addFirst(lorraine);
list.addFirst(dominic);
list.add(jessica); // add and addLast are the same, add to end of linkedlist
printList(list);
// for(Employee employee: linkedlist){
// System.out.println(employee);
// }
list.removeFirst(); // remove and removeFirst are the same, remove from front of the linkedlist
printList(list);
list.removeLast();
printList(list);
}
public static void printList(LinkedList list){
Iterator iterator = list.iterator();
System.out.println("HEAD -> ");
while(iterator.hasNext()){
System.out.print(" " + iterator.next());
System.out.println(" <=> ");
}
System.out.println("null\n");
}
} |