Java 链表

LinkedList.java

/**
 * void deleteLast() 删除最后一个元素
 * void delete(int k) 删除第 k 个元素
 * boolean find(LinkedList list, String key) 查找链表中是否存在某个结点的值域为 key
 * void removeAfter(Node node) 删除该结点的后续结点
 * void insertAfter(Node node1, Node node2) 将第二个结点放在第一个结点后面
 * void remove(LinkedList list, String key) 删除所有值为 key 的结点
 * int max(LinkedList first) 接收一个首结点，返回值最大的结点的值，为空返回 0
 * int max(LinkedList first) 用递归解决 
 */
 
public class LinkedList<Item> {

	private Node first; 

	class Node {
		private Item item;
		private Node next;
		
		public Node() {
		}
		
		public Node(Item item) {
			this.item = item;
			this.next = null;
		}
	}

	public LinkedList() {
		first = null;
	}

//	插入元素
	public void add(Item item) {
		Node newNode = new Node();
		newNode.item  = item;
		
		if(isEmpty()) {
			first = newNode;
			return;
		}
		
		Node temp = first;
		
		while(temp.next != null) {
			temp = temp.next;
		}
		temp.next = newNode;
	}


//	插入元素，直接插入结点
	public void add(Node newNode) {

		if(first == null) {
			first = newNode;
			return;
		}
		
		Node temp = first;
		
		while(first != null && temp.next != null) {
			temp = temp.next;
		}
		
		temp.next = newNode;
	}
	
	public boolean isEmpty() {
		return first == null;
	}
	
//	删除最后一个元素
//  涉及删除操作的，通常使用两个 Node
	public void deleteLast() {
//		如果链表为空，就不用删除
		if(isEmpty()) return;
		
//		如果只有一个元素，first 就指向 null
		if(first.next == null) first = null;
		
//		使用两个元素，找到最后一个元素
		Node before = first;
		Node after = before.next;
		
		while(after.next != null) {
			before = after;
			after = after.next;
		}
		
		before.next = null;
	}
	
//	删除第 k 个元素
	public void delete(int k) {
//		链表为空直接返回
		if(isEmpty() || k < 1) return;
		
//		要删除第一个元素的话，first 指向 first.next
		if(k == 1) {
			first = first.next;
			return;
		}

//		排除以上两种情况之后，从第二个元素（after）开始对比 k
//		如果 i == k，before.next = after.next

		Node before = first;

		Node after = first.next;

		for(int i = 2; i <= k && after != null; i++) {
			if(i == k) {
				before.next = after.next;
				break;
			}
			before = after;
			after = after.next;
		}
	}
	
//	查找链表中是否存在某个结点的值域为 key
//	泛型类非要指定一个类型，如果故意不按规则调用就会出错
	public boolean find(LinkedList<Item> list, String key) {
		Node temp = list.first;
		
		while(temp != null) {
			if(temp.item.equals(key)) {
				return true;
			}
			temp = temp.next;
		}
		return false;
	}
	
//	删除某个结点之后的结点
	public void removeAfter(Node node) {
		if(node == null || node.next == null) return;
		
		Node temp = first;
		
		while(temp != null) {
			if(node == temp) {
				break;
			}
			temp = temp.next;
		}
		
//		到这一步，要么是 temp == node，要么是 temp == null
//		若是前者，temp.next = null，即可删除后面的元素。
		if(temp != null) {
			temp.next = null;
		}
	}
	
//	将第二个结点插入链表，并使之成为第一个结点的后续结点。node1 应该已经存在于链表
	public void insertAfter(Node node1, Node node2) {
		if(node1 == null || node2 == null) return;
		
		Node temp = first;
		
		while(temp != null) {
			if(temp == node1) {
				node2.next = node1.next;
				node1.next = node2;
				break;
			}
			temp = temp.next;
		}
	}
	
//	删除所有值为 key 的结点
	public void remove(LinkedList<Item> list, String key) {
		Node temp = first;
		while(temp != null && temp.item.equals(key)) {
			first = temp.next;
			temp = first;
		}

		if(temp == null) return;
		
		Node before = temp;
		Node after = temp.next;
		
		while(after != null) {
			if(after.item.equals(key)) {
				before.next = after.next;
				after = after.next;
			} else {
				before = after;
				after = after.next;
			}
		}
	}

//	返回链表结点中最大的那个数字
	public int max(LinkedList<Integer>.Node head) {
		if(head == null) return 0;
		
		int max = head.item;
		head = head.next;
		
		while(head != null) {
			if(head.item > max) {
				max = head.item;
			}
			head = head.next;
		}
		
		return max;
	}
	
//	用递归解决
	public int max2(LinkedList<Integer>.Node head) {
		if(head == null) return 0;
		
		if(head.next == null) return head.item;
		
		int cur = head.item;
		int oth = max2(head.next);
		
		return cur > oth ? cur : oth;
	}
	
	public void display() {
		Node temp = first;
		
		while(temp != null) {
			System.out.print(temp.item + " ");
			temp = temp.next;
		}
		System.out.println();
	}
	
	/**
	 * 创建内部类对象必须创建外部类对象。
	 * @param key
	 * @return
	 */
	public Node getANode(Item key) {
		return new Node(key);
	}
	
}