SLL

Complete

Succeeds: lists

Summary

Singly linked list

implements list ADT

Operation	Method	Performance
`get(i)`	list traversal	- , first element - , last element
`search(v)`	linear search	- , first element - , last element/not found
`insert(i, v)`	traverse the list and insert the node	- , insert at head, shift head pointer - , insert into empty list, need to set the tail pointer - , insert in between - , insert after tail, shift tail pointer
`remove(i)`	traverse the list and remove the node	- , remove at head - , remove in between - , remove at tail, traverse list to set tail pointer

Strengths

fast insertion and extraction at the head
fast insertion at the tail
overcomes compact array’s fixed size issue

Limitations

indexing requires traversal
slow extraction from tail

Concept

Data structure

series of nodes
pointer to next node
non-contiguous

java

class Node {
	Object data;
	Node next;
}

Application

Leetcode: Delete the Middle Node of a Linked List

naive double traversal

java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
public ListNode deleteMiddle(ListNode head) {
		int idx = Math.floorDiv(length(head, 1), 2); // O(n)
		removeNode(head, idx - 1); // O(n)
		if (idx == 0)
				return null;
		else
				return head;
}

public int length(ListNode node, int length) {
		if (node.next != null)
				return length(node.next, ++length);
		else
				return length;
}

public void removeNode(ListNode node, int idx) {
		if (idx > 0)
				removeNode(node.next, --idx);
		else if (node.next != null && node.next.next != null)
				node.next = node.next.next;
		else
				node.next = null;
}

two pointer approach(slow and fast)

java

public ListNode deleteMiddle(ListNode head) {
	if (head == null || head.next == null) return null; // empty or single item case
	ListNode slow = head, fast = head.next.next;
	while (fast != null && fast.next != null) {
		slow = slow.next;
		fast = fast.next.next;
	}
	slow.next = slow.next.next;
	return head;
}