java链表之--java双向链表的增删改查

柔光的暖阳◎ 2022-09-23 05:58 121阅读 0赞

单向链表只能从一个方向遍历链表，即只能查找结点的下一个结点（后继结点），而不能查找结点的上一个结点（前驱结点）。鉴于上述问题，引入了**双向链表**。由于双向循环链表包含双向链表的所有功能操作。因此，我们只讲述双向循环链表。

与单向链表不同，双向链表的结点构造如下图所示。即一个结点由三个部分组成，数据域DATA，左指针域pre和右指针域next。其中，数据域用来存放结点数据信息，左指针域用来指向前驱结点，右指针域用来指向后继结点。

![Image 1][]

class DoubleLinkedList {
    	// 节点类Node 定义，区别于单向!-----主要使用前后节点替换来操作---画图会清晰，掌握后面几种方法
    	private static class Node {
    		Object value;
    		Node prev = this;
    		Node next = this;
    
    		Node(Object v) {
    			value = v;
    		}
    
    		public String toString() {
    			return value.toString();
    		}
    	}
    
    	private Node head = new Node(null); // 头节点
    	private int size; // 链表大小
    
    	// 以下是接口方法
    	public boolean addFirst(Object o) {
    		addAfter(new Node(o), head);
    		return true;
    	}
    
    	public boolean addLast(Object o) {
    		addBefore(new Node(o), head);
    		return true;
    	}
    
    	public boolean add(Object o) {
    		return addLast(o);
    	}
    
    	public boolean add(int index, Object o) {
    		addBefore(new Node(o), getNode(index));
    		return true;
    	}
    
    	public boolean remove(int index) {
    		removeNode(getNode(index));
    		return true;
    	}
    
    	public boolean removeFirst() {
    		removeNode(head.next);
    		return true;
    	}
    
    	public boolean removeLast() {
    		removeNode(head.prev);
    		return true;
    	}
    
    	public Object get(int index) {
    		return getNode(index).value;
    	}
    
    	public int size() {
    		return size;
    	}
    
    	public String toString() {
    		StringBuffer s = new StringBuffer("[");
    		Node node = head;
    		for (int i = 0; i < size; i++) {
    			node = node.next;
    			if (i > 0)
    				s.append(", ");
    			s.append(node.value);
    		}
    		s.append("]");
    		return s.toString();
    	}
    
    	// 以下是实现方法
    	private Node getNode(int index) {
    		if (index < 0 || index >= size)
    			throw new IndexOutOfBoundsException();
    		Node node = head.next;
    		for (int i = 0; i < index; i++)
    			node = node.next;
    		return node;
    	}
    
    	private void addBefore(Node newNode, Node node) {
    		newNode.next = node;
    		newNode.prev = node.prev;
    		newNode.next.prev = newNode;
    		newNode.prev.next = newNode;
    		size++;
    	}
    
    	private void addAfter(Node newNode, Node node) {
    		newNode.prev = node;
    		newNode.next = node.next;
    		newNode.next.prev = newNode;
    		newNode.prev.next = newNode;
    		size++;
    	}
    
    	private void removeNode(Node node) {
    		node.prev.next = node.next;
    		node.next.prev = node.prev;
    		node.prev = null;
    		node.next = null;
    		size--;
    	}
    }
    
    // 有些地方还可以优化，比如查找时可以使用折半查找。
    // 测试类：
    public class DoubleLink {
    	public static void main(String[] args) {
    		DoubleLinkedList dll = new DoubleLinkedList();
    		// 添加
    		dll.add("aaa");
    		dll.add("bbb");
    		dll.add("ccc");
    		System.out.println(dll);
    		// 添加到最前
    		dll.addFirst("AAA");
    		System.out.println(dll);
    		// 添加到最后，同添加
    		dll.addLast("CCC");
    		System.out.println(dll);
    		// 添加到指定位置
    		dll.add(4, "DDD");
    		System.out.println(dll);
    		// 移除最前的
    		dll.removeFirst();
    		System.out.println(dll);
    		// 移除最后的
    		dll.removeLast();
    		System.out.println(dll);
    		// 移除指定位置上的
    		dll.remove(2);
    		System.out.println(dll);
    		// 返回指定位置上的元素
    		System.out.println(dll.get(1));
    	}
    }

\[aaa, bbb, ccc\]  
\[AAA, aaa, bbb, ccc\]  
\[AAA, aaa, bbb, ccc, CCC\]  
\[AAA, aaa, bbb, ccc, DDD, CCC\]  
\[aaa, bbb, ccc, DDD, CCC\]  
\[aaa, bbb, ccc, DDD\]  
\[aaa, bbb, DDD\]  
bbb

[Image 1]: