Linked List

---

Linked List

Arrays are limited by their static structures. You cannot easily extend or reduce them. It is expensive to delte/insert from the front or middle of the array.

A linked list is a linear data structure where each element is a separate object made up of at least two items: the data, and a reference to the next element (called "node").

• The entry point to a linked list is called the head. It is not a node, but a reference to the first node.
• The last node has a reference to null.
• The Node class (declared as satic) is commonly nested inside the LinkedList class, eliminating the need for getters/setters.
  • Static nested class do not have access to the instance members of the outer class while the outer class has access to the instance members of the staic nested cass objects.

Disadvantages vs Arrays Linked Lists do not allow direct access to individual elements. You always have to start at the head. It also uses more memory than an array

Implementation

Node:

class Node {
	int data;
	int next;
	Node(int data) {
		this.data = data;
		this.next =null; //default
	}
}

Prepend to the front of the list

public void addFirst(T t) {
	Node<T> node = new Node<>(t);
	node.next = head;
	head = node;
}

Traverse through the list:

public void traverse() {
	Node<T> current = head;
	while (current != null) {
		System.out.println(current.data);
		current = current.next;
	}
}

Get (failes fails for an edge case):

public T get(int index) {
	return find(index).data;
}

private Node<T> find(int index) {
	Node<T> target = head;
	while (int i = 0; i < index; i++) {
		target = target.next;
	}
	return target; 
}

Append to the end (fails for edge case); you can implement with a counter controlled loop if you have a counter controlled loop.:

public void addLast(T t) {
	Node<T> tail = head;
	while (tail.next != null) { 
		tail = tail.next;
	}
	tail.next = new Node<T>(t);
}

Insert at a specific index (fails for edge case):

public void insert(int index, T t) {
	Node<T> target = head;
	for (int i = 0; i < index-1, i++) {
		target = target.next;
	}
	Node<T> node = new Node(t);
	node.next = target.next;
	target.next = node;
}

Delete opeartion:

public void delete (int index) {
	Node<T>  beforeTarget = head;
	for (int i = 0; i < index - 1; i ++) {
		beforeTarget = beforeTarget.next;
	}
	beforeTarget.next = beforeTarget.next.next;
}

Iterator:

private class LinkedListIterator implements Iterator<T> {
	private Node<T> current; 
	public LinkedListIterator(Node<T> head) { 
		current = head;
	} 
	
	@Override public T next() {
		if (!hasNext()) {
			throw new NoSuchElementException();
		} 
		T t = current.data; 
		current = current.next; 
		return t; 
	} 
	
	@Override public boolean hasNext() { 
		return current != null;
	} 
}