单向循环链表和双向循环链表的结构分析

一、单向循环链表

• 单向循环链表：

  如果把单链表的最后一个节点的指针指向链表头部，而不是指向NULL，那么就构成了一个单向循环链表，通俗讲就是把尾节点的下一跳指向头结点。

单向循环链表 –多个节点

单向循环链表 – 只有1个节点

对于和我们之前学的单向链表相比，单向循环链表的区别在于其尾节点指向链表的首节点，我们在单链表（Linked List）的clear、add、remove、indexOf以及toString方法的底层封装的博客上面可以改动的也无非就是添加和删除的操作。

（一）单向循环链表 — add(int index, E element)

@Override
public void add(int index, E element) {
	rangeCheckForAdd(index);
	
	if (index == 0) {
		//先不要修改first，因为要是修改了；再找最后一个节点的时候会发生变化
		Node<E> newFirst = new Node<>(element, first);
		// 拿到最后一个节点
		Node<E> last = (size == 0) ? newFirst : node(size - 1);
		last.next = newFirst;
		first = newFirst;
	} else {
		Node<E> prev = node(index - 1);
		prev.next = new Node<>(element, prev.next);
	}
	size++;
}
           

（二）单向循环链表 — remove(int index)

@Override
public E remove(int index) {
	rangeCheck(index);
	
	Node<E> node = first;
	if (index == 0) {
		if (size == 1) {
			first = null;
		} else {
			//先拿到最后一个节点
			Node<E> last = node(size - 1);
			//再改变first节点
			first = first.next;
			last.next = first;
		}
	} else {
		Node<E> prev = node(index - 1);
		node = prev.next;
		prev.next = node.next;
	}
	size--;
	return node.element;
}
           

（三）单向循环链表 — node中的toString方法

private static class Node<E> {
	E element;
	Node<E> next;
	public Node(E element, Node<E> next) {
		this.element = element;
		this.next = next;
	}
	
	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		sb.append(element).append("_").append(next.element);
		return sb.toString();
	}
}
           

（四）测试

import com.mj.circle.SingleCircleLinkedList;
public class Main {
	static void testList(List<Integer> list) {
		list.add(11);
		list.add(22);
		list.add(33);
		list.add(44);

		list.add(0, 55); // [55, 11, 22, 33, 44]
		list.add(2, 66); // [55, 11, 66, 22, 33, 44]
		list.add(list.size(), 77); // [55, 11, 66, 22, 33, 44, 77]

		list.remove(0); // [11, 66, 22, 33, 44, 77]
		list.remove(2); // [11, 66, 33, 44, 77]
		list.remove(list.size() - 1); // [11, 66, 33, 44]		
		System.out.println(list);
	}
	public static void main(String[] args) {
		 testList(new SingleCircleLinkedList<>());	
	}
}
运行结果：
size=4, [11_66, 66_33, 33_44, 44_11]
           

二、双向循环链表

双向循环链表 –多个节点

双向循环链表 – 只有1个节点

• 双向循环链表：双（向）链表中有两条方向不同的链，即每个结点中除next域存放后继结点地址外，还增加一个指向其直接前趋的指针域prior。

（一）单向循环链表 — add(int index, E element)

@Override
public void add(int index, E element) {
	rangeCheckForAdd(index);

	// size == 0
	// index == 0
	if (index == size) { // 往最后面添加元素
		Node<E> oldLast = last;
		last = new Node<>(oldLast, element, first);
		if (oldLast == null) { // 这是链表添加的第一个元素
			first = last;
			first.next = first;
			first.prev = first;
		} else {
			oldLast.next = last;
			first.prev = last;
		}
	} else {
		Node<E> next = node(index); 
		Node<E> prev = next.prev; 
		Node<E> node = new Node<>(prev, element, next);
		next.prev = node;
		prev.next = node;
		
		if (next == first) { // index == 0
			first = node;
		}
	}
	
	size++;
}
           

（二）单向循环链表 — remove(int index)

@Override
public E remove(int index) {
	rangeCheck(index);
	return remove(node(index));
}

private E remove(Node<E> node) {
	if (size == 1) {
		first = null;
		last = null;
	} else {
		Node<E> prev = node.prev;
		Node<E> next = node.next;
		prev.next = next;
		next.prev = prev;
		
		if (node == first) { // index == 0
			first = next;
		}
		
		if (node == last) { // index == size - 1
			last = prev;
		}
	}
	
	size--;
	return node.element;
}
           

（三）单向循环链表 — node中的toString方法

private static class Node<E> {
E element;
	Node<E> prev;
	Node<E> next;
	public Node(Node<E> prev, E element, Node<E> next) {
		this.prev = prev;
		this.element = element;
		this.next = next;
	}
	
	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		
		if (prev != null) {
			sb.append(prev.element);
		} else {
			sb.append("null");
		}
		
		sb.append("_").append(element).append("_");

		if (next != null) {
			sb.append(next.element);
		} else {
			sb.append("null");
		}
		
		return sb.toString();
	}
}
           

（四）测试

import com.mj.circle.CircleLinkedList;
public class Main {
	static void testList(List<Integer> list) {
		list.add(11);
		list.add(22);
		list.add(33);
		list.add(44);

		list.add(0, 55); // [55, 11, 22, 33, 44]
		list.add(2, 66); // [55, 11, 66, 22, 33, 44]
		list.add(list.size(), 77); // [55, 11, 66, 22, 33, 44, 77]

		list.remove(0); // [11, 66, 22, 33, 44, 77]
		list.remove(2); // [11, 66, 33, 44, 77]
		list.remove(list.size() - 1); // [11, 66, 33, 44]
		
		System.out.println(list);
	}

	public static void main(String[] args) {
		 testList(new CircleLinkedList<>());
	}
}
运行结果：
size=4, [44_11_66, 11_66_33, 66_33_44, 33_44_11]