链表

• 1.前言
• 2.定义
• 3.模板设计
• 4.单链表
• • 4.1概念
  • 4.2基本操作
  • • 4.2.1添加
    • 4.2.2删除
    • 4.2.3修改
    • 4.2.4查询
• 5.双向链表
• • 5.1概念
  • 5.2基本操作
  • • 5.2.1添加
    • 5.2.2删除
    • 5.2.3修改
    • 5.2.4查询
• 6.单向循环链表
• • 6.1概念
  • 6.2基本操作
  • • 6.2.1添加
    • 6.2.2删除
    • 6.2.3修改
    • 6.2.4查询
• 7.双向循环链表
• • 7.1概念
  • 7.2基本操作
  • • 7.2.1添加
    • 7.2.2删除
    • 7.2.3修改
    • 7.2.4查询

1.前言

前面我们已经学习了数组，数组容量一经定义难以改变，同时删除和插入元素需要移动大量的数据元素，效率较低。为此，引入了线性表中的链式存储结构。链式存储的数据元素不再具有连续的地址，同时可以根据需要随时申请和释放空间，更加灵活高效，但是丧失了随机访问的能⼒。

2.定义

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，是一种递归的数据结构，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

3.模板设计

设计一个List接口，里面写一些通用的操作，供其他类实现，创建抽象类AbstractList，继承List接口，实现一些通用的操作，比如判断索引是否越界之类的常用操作。

List接口

public interface List<E> { 
	static final int ELEMENT_NOT_FOUND = -1;
	
	void clear();

	
	int size();

	
	boolean isEmpty();

	
	boolean contains(E element);

	
	void add(E element);

	
	E get(int index);

	
	E set(int index, E element);

	
	void add(int index, E element);

	
	E remove(int index);

	
	int indexOf(E element);
}

抽象类AbstractList

public abstract class AbstractList<E> implements List<E>  { 
	
	protected int size;
	
	public int size() { 
		return size;
	}

	
	public boolean isEmpty() { 
		 return size == 0;
	}

	
	public boolean contains(E element) { 
		return indexOf(element) != ELEMENT_NOT_FOUND;
	}

	
	public void add(E element) { 
		add(size, element);
	}
	
	protected void outOfBounds(int index) { 
		throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
	}
	
	protected void rangeCheck(int index) { 
		if (index < 0 || index >= size) { 
			outOfBounds(index);
		}
	}
	
	protected void rangeCheckForAdd(int index) { 
		if (index < 0 || index > size) { 
			outOfBounds(index);
		}
	}
}

4.单链表

4.1概念

顾名思义，单链表就是表示数据结点只有一个指针域。同时在单链表具体功能的实现中，为了让代码更加精简，统一所有节点的处理逻辑，可以在最前面增加一个虚拟的头结点的辅助结点（不存储数据）。同时，由于单链表的表头元素中没有前驱，所以创建一个指向表头结点的指针，来存储表头结点的地址，称为单链表的头指针变量，即下图中的first。

4.2基本操作

为了更好的实现下面的增删改查操作，我们首先首先用一个静态内部类来定义结点的抽象数据类型

	private static class Node<E> { 
		E element;
		Node<E> next;
		public Node(E element, Node<E> next) { 
			this.element = element;
			this.next = next;
		}
	}

一个 Node 对象含有两个实例变量，类型分别为 E（参数类型） 和 Node。其中next用来指向下一个链表，element用来存储一个结点的数据。我们会在需要使用 Node 类的类中定义它并将它标记为 private，因为它不是为用例准备的。
然后创建一个first指针，指向头结点。

private Node<E> first;

我们再写一个node方法，用来获取index位置对应的节点对象。首先检查index值是否合理，如果合理，创建结点node指向头结点。进行index次循环，每次让结点node指向下一个结点。循环结束返回node。

	private Node<E> node(int index) { 
		rangeCheck(index);
		
		Node<E> node = first.next;
		for (int i = 0; i < index; i++) { 
			node = node.next;
		}
		return node;
	}

同时重写indexOf方法，用来获取元素的位置，具体操作与上面类似

	@Override
	public int indexOf(E element) { 
		if (element == null) { 
			Node<E> node = first;
			for (int i = 0; i < size; i++) { 
				if (node.element == null) return i;
				
				node = node.next;
			}
		} else { 
			Node<E> node = first;
			for (int i = 0; i < size; i++) { 
				if (element.equals(node.element)) return i;
				
				node = node.next;
			}
		}
		return ELEMENT_NOT_FOUND;
	}

4.2.1添加

如果要在index=0位置处插入元素，只需要让虚拟头结点的next指向新插入的结点，新插入结点的next指向原先0位置的结点。

如果在其他合理位置插入，只需要找到前一个结点，让他的next指向新插入的结点，新插入结点的next指向原先位置的结点。

	@Override
	public void add(int index, E element) { 
		rangeCheckForAdd(index);
		
		Node<E> prev = index == 0 ? first : node(index - 1);
		prev.next = new Node<>(element, prev.next);

		size++;
	}

4.2.2删除

如果删除index=0位置处的结点，只需要让虚拟头结点的next指向index=1处的结点。在Java中，0位置指向1位置的next不用设置为null，曾经的结点对象没有其他结点指向它，变成了"孤儿"，Java 的内存管理系统最终将回收它所占用的内存。

如果删除其他位置的结点，只需要找到待删除元素的前一个结点，让它指向待删除元素的下一个结点。

	@Override
	public E remove(int index) { 
		rangeCheck(index);
		
		Node<E> prev = index == 0 ? first : node(index - 1);
		Node<E> node = prev.next;
		prev.next = node.next;
			
		size--;
		return node.element;
	}

4.2.3修改

	@Override
	public E set(int index, E element) { 
		Node<E> node = node(index);
		E old = node.element;
		node.element = element;
		return old;
	}

4.2.4查询

@Override
	public E get(int index) { 
		return node(index).element;
	}

5.双向链表

5.1概念

看图就知道，双向链表与单链表的不同之处在于每个结点都增加了一个指向其前驱的指针域，其余不变。同时呢，为了更好的操作，我们再添加一个first指针指向第一个结点，一个last指针指向最后一个结点。

当只有一个元素时

5.2基本操作

与单链表的操作类似，创建一个内部类Node

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;
		}
	}

然后创建first和last指针分别指向第一个结点和最后一个结点。

private Node<E> first;
private Node<E> last;	

5.2.1添加

如果原先链表不为空，我们在链表最后添加元素。

1. 我们先拿到原先的last，就命名为oldLast
2. 让新添加的node前驱结点指向oldLast，后驱结点指向null，然后让last指向新添加的结点，
3. 让oldLast的next指向新添加的结点。

当链表为空时，添加第一个元素，即oldLast为null，只需要first=last

同样链表有其他结点，我们在非首尾位置添加结点。

1. 通过node(index)获取到原先位置的结点，命名为next，
2. 通过next.prev获取原先node位置的前驱元素prev，让新添加的node元素的前驱结点指向prev,后驱结点指向next，
3. 通过next.prev = node指向新添加的元素，最后通过prev.next = node让前驱元素指向新添加的元素node。

当添加在0位置的元素时，前面获取的prev元素为null，只需要让first指向新添加的node

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

5.2.2删除

当链表结构如上图时，删除最后一个元素

1. 通过node(3)获取要删除的元素node,然后分别获取到它的前驱结点prev和后继结点next。
2. 通过prev.next = next使前驱结点指向null
3. 最后让last指向prev

当删除第一个元素时

1. 通过node(0)获取要删除的元素node,然后分别获取到它的前驱结点prev和后继结点next。
2. 发现prev=null,则直接first=next，指向待删元素的下一个结点
3. 最后next.prev = prev，其实这里的prev==null

当删除非首尾结点时

1. 通过node(index)获取要删除的元素node,然后分别获取到它的前驱结点prev和后继结点next。
2. 通过prev.next = next使前驱结点指向被删元素的后一个结点
3. 最后next.prev = prev，使被删元素的后一个结点next指向被删元素的前一个结点perv

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

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

5.2.3修改

@Override
	public E set(int index, E element) { 
		Node<E> node = node(index);
		E old = node.element;
		node.element = element;
		return old;
	}

5.2.4查询

	@Override
	public E get(int index) { 
		return node(index).element;
	}

6.单向循环链表

6.1概念

为了某些操作实现方便，常将单链表中的最后一个结点的指针域指向头结点，这样就形成了首尾相连的结构，称为循环单链表。

当只有一个结点时，结点的next指向自己，如下图

6.2基本操作

先创建一个内部类Node

private static class Node<E> { 
		E element;
		Node<E> next;
		public Node(E element, Node<E> next) { 
			this.element = element;
			this.next = next;
		}
	}

然后创建first指向第一个结点。

private Node<E> first;

6.2.1添加

当添加元素的位置为0时

1. 我们先让待插入结点newFirst的next指向原先0号位置的结点
2. 如果此时的链表不为空，即size!=0,通过node(index-1)获取最后一个结点。如果此时链表为空，最后一个结点就是它自己，让它的next指向它自己。然后让最后一个结点的next指向newFirst
3. 此时的first还指向原先的第一个结点，最后将它的指针引向newFirst,即first = newFirst

当添加的元素位置不为0时

1. 首先获取待添加位置的前一个元素，比如添加新结点到三号位置，先通过node(index-1)获取前一个元素prev
2. 让prev的next指向新插入的结点，让新插入结点的next指向原先位置的元素

    @Override
	public void add(int index, E element) { 
		rangeCheckForAdd(index);
		
		if (index == 0) { 
			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++;
	}

6.2.2删除

当删除元素为第一个时

1. 首先判断这个链表是不是只含这一个元素，如果只含这一个，只需要first=null,没有指针引向它，它就会被回收，也就达到了删除的目的。
2. 如果还有其它的元素，首先将first指向原先一号位置的元素，即first = first.next，然后通过node(size - 1)获取最后一个元素，使其指向原先的一号位置元素，即last.next = first
   

当删除元素不是第一个时
1.通过node(index - 1)获取待删除元素的前一个结点prev，只需要让前一个结点的next指向待删除元素的的next，即prev.next = prev.next.next

@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.next;
				last.next = first;
			}
		} else { 
			Node<E> prev = node(index - 1);
			node = prev.next;
			prev.next = node.next;
		}
		size--;
		return node.element;
	}

6.2.3修改

@Override
	public E set(int index, E element) { 
		Node<E> node = node(index);
		E old = node.element;
		node.element = element;
		return old;
	}

6.2.4查询

	
	private Node<E> node(int index) { 
		rangeCheck(index);
		
		Node<E> node = first;
		for (int i = 0; i < index; i++) { 
			node = node.next;
		}
		
		return node;
	}

@Override
	public E get(int index) { 
		return node(index).element;
	}

7.双向循环链表

7.1概念

双向循环链表的节点不仅包含指向下一个节点的指针(next)，还包含指向前一个节点的指针(prev)，并且有循环链表的特点，最后一个结点的next指向第一个结点。

当链表只有一个元素时：

7.2基本操作

与单链表的操作类似，创建一个内部类Node

	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;
		}
	}

然后创建first和last指针分别指向第一个结点和最后一个结点。

private Node<E> first;
private Node<E> last;	

7.2.1添加

@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++;
	}

7.2.2删除

public E remove(int index) { 
		rangeCheck(index);

		Node<E> node = node(index);
		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;
	}

7.2.3修改

@Override
	public E set(int index, E element) { 
		Node<E> node = node(index);
		E old = node.element;
		node.element = element;
		return old;
	}

7.2.4查询

	private Node<E> node(int index) { 
		rangeCheck(index);
		
		if (index < (size >> 1)) { 
			Node<E> node = first;
			for (int i = 0; i < index; i++) { 
				node = node.next;
			}
			return node;
		} else { 
			Node<E> node = last;
			for (int i = size - 1; i > index; i--) { 
				node = node.prev;
			}
			return node;
		}
	}

@Override
	public E get(int index) { 
		return node(index).element;
	}