开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 【恋上数据结构与算法】理论三：链表：Linked List -> 正文阅读

[数据结构与算法]【恋上数据结构与算法】理论三：链表：Linked List

一、比较

1.1 动态数组

动态数组的缺点：可能会造成内存空间的大量浪费
动态数组是一种顺序存储，所有元素的内存地址是连续的

1.2 链表

用多少内存就申请多少内存
链表是一种链式存储的线性表，所有元素的内存地址不一定是连续的

在这里插入图片描述

二、链表

2.1 接口设计

创建 LinkedList 类，用来管理链表数据，其中的 size 属性记录存储数据的数量，first 属性引用链表的第 0 个元素
创建私有类 Node，其中的 element 属性用于存储元素， next 属性用于指向链表中的下一个节点

在这里插入图片描述

public class LinkedList<E> {
    private int size;
    private Node<E> first;
    
    // 元素的数量
    int size(); 
    // 是否为空
    boolean isEmpty();
    // 是否包含某个元素
    boolean contains(E element); 
    // 添加元素到最后面
    void add(E element); 
    // 返回index位置对应的元素
    E get(int index); 
    // 设置index位置的元素
    E set(int index, E element); 
    // 往index位置添加元素
    void add(int index, E element); 
    // 删除index位置对应的元素 
    E remove(int index); 
    // 查看元素的位置
    int indexOf(E element); 
    // 清除所有元素
    void clear();
    
    // 私有类, 链表中的节点
    private class Node<E> {
        E element;
        Node<E> next;
        // 构造方法
        public Node(E element, Node<E> next) {
            this.element = element;
            this.next = next;
        }
    }
}

2.2 方法实现

在这里插入图片描述

2.2.1 构造方法

链表的创建与动态数组不同，动态数组在构造时需要传入一个空间属性，来决定这个数组的容量。但链表元素是在添加时才创建的，内存地址不一定是连续的。所以链表不需要在单独设计构造方法，使用默认构造方法即可

2.2.2 添加元素

添加数据时，需要创建一个节点存储数据，并将该节点拼接到最后节点的后面，然后 size加1
需要区分当前链表没有数据，新节点拼接到 first 和当前链表有数据，新节点拼接到最后的节点

public void add(E element) {
    // 当first等于null时, 说明此事没有节点, 所以first引用新节点
    if (first == null) {
    	first = new Node<E>(element, null);
    }
    // 当fitst不等于null时, 说明链表中有节点, 此时获取最后一个节点, 并将该节点的next指向新节点
    else {
        Node<E> node = node(size - 1);
        node.next = new Node<E>(element, null);
    }
    size++;
}

2.2.3 插入元素

插入链表，首先需要创建新节点，然后通过变更插入位置前一个元素 next 指针指向，插入指定位置即可
需要区分插入到 0 的位置，使用 first 指向新节点和插入到非 0 位置，找到前一个节点进行处理两种情况

2.2.3.1 数组越界

插入元素的位置必须不能小于0, 也不能大于等于size ，所以我们在插入元素之前需要先进行索引检查

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

插入元素代码如下：

在编写链表过程中，要注意边界测试、如 index 为0、size - 1、size时的情况

public void add(int index, E element) {
    // 检查索引是否越界
    rangeCheckForSize(index);
    // 当插入到0的位置时
    if (index == 0) {
        // 将first指向新节点, 新节点的next指向first之前指向的节点
        first = new Node<E>(element, first.next);
    }else {
        // 找到指定位置前面的节点
        Node<E> prev = node(index - 1);
        // 将前面节点的next指向新节点, 新节点的next指向prev之前指向的节点
        prev.next = new Node<>(element, prev.next);
    }
    size++;
}

添加元素也可以简写：

public void add(E element) {
    // 元素添加到size位置, 即添加到最后面
    add(size, element);
}

2.2.4 删除元素

首先找到删除节点（delete_node）的前一个节点（pre_node），然后通过变更（pre_node）节点 next 指针指向删除节点（delete_node）的下一个节点即可，然后 size 减 1
需要判断是否删除的第 0 个元素，如果是，则使用 first 指向第1个节点

public E remove(int index) {
    // 检查索引是否越界
    rangeCheck(index);
    // 记录需要删除的节点
    Node<E> old = first;
    // 当删除第0个元素时, 将first的next指向索引为`1`的节点即可
    if (index == 0) {
        first = first.next;
    }else {
        // 找到前一个元素
        Node<E> prev = node(index - 1);
        // 记录需要删除的节点
        old = prev.next;
        // 将prev的next指向需要删除节点的后一个节点
        prev.next = old.next;
    }
    // size-1
    size--;
    // 返回删除的元素
    return old.element;
}

2.2.5 清空元素

将 first 指向 null，释放链表所有 node ，同时 size 置为 0 即可

在这里插入图片描述

public void clear() {
    first = null;
    size = 0;
}

2.2.6 修改元素

首先通过遍历链表元素，找到该节点

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

然后修改 node 节点的 element 即可

public E set(int index, E element) {
    // 找到对应节点, node方法中已经判断了索引是否越界
    Node<E> node = node(index);
    // 记录旧元素
    E old = node.element;
    // 覆盖元素
    node.element = element;
    // 返回旧元素
    return old;
}

2.2.7 查找元素

找到对应的节点, 取出元素即可

public E get(int index) {
    // node方法中已经判断了索引是否越界
    return node(index).element;
}

2.2.8 查找元素索引

查找指定元素的索引，需要遍历所有节点，找到节点对应的元素与执行元素相等即可
如果需要支持节点 element 为 null ，则需要分两种情况处理

private static final int ELEMENT_ON_FOUND = -1;
public int indexOf(E element) {
    // 取出头结点
    Node<E> node = first;
    // 当element为null时的处理
    if (element == null) {
        // 遍历节点, 找到存储为null的节点, 返回索引
        for (int i = 0; i < size; i++) {
            if (node.element == null) return i;
            node = node.next;
        }
    }else {
        for (int i = 0; i < size; i++) {
            // 遍历节点, 找到存储的元素与指定元素相等的节点, 返回索引
            if (element.equals(node.element)) return i;
            node = node.next;
        }
    }
    // 没有找到元素对应的节点, 返回ELEMENT_ON_FOUND
    return ELEMENT_ON_FOUND;
 }

2.2.9 获取链表存储元素的个数

获取链表存储元素的个数, 就是 size 的值

public int size() {
    return size;
}

2.2.10 链表是否为空

链表是否为空, 只需要判断 size 是否等于 0 即可

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

2.2.11 判断元素是否存在

判断元素是否存在, 只需要判断元素的索引是否为 ELEMENT_ON_FOUND 即可

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

2.2.12 打印链表中存储的数据

public String toString() {
    StringBuilder string = new StringBuilder();
    string.append("size = ").append(size).append(", [");
    Node<E> node = first;
    for (int i = 0; i < size; i++) {
        if (i != 0) {
            string.append(",");
        }
        string.append(node.element);
        node = node.next;
    }
    string.append("]");
    return string.toString();
}

2.3 链表的复杂度

在这里插入图片描述

2.4 完整代码

2.4.1 AbstractList.java

package com.mj;

public abstract class AbstractList<E> implements List<E>  {
	/**
	 * 元素的数量
	 */
	protected int size;
	/**
	 * 元素的数量
	 * @return
	 */
	public int size() {
		return size;
	}

	/**
	 * 是否为空
	 * @return
	 */
	public boolean isEmpty() {
		 return size == 0;
	}

	/**
	 * 是否包含某个元素
	 * @param element
	 * @return
	 */
	public boolean contains(E element) {
		return indexOf(element) != ELEMENT_NOT_FOUND;
	}

	/**
	 * 添加元素到尾部
	 * @param element
	 */
	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);
		}
	}
}

2.4.2 List.java

package com.mj;

public interface List<E> {
	static final int ELEMENT_NOT_FOUND = -1;
	/**
	 * 清除所有元素
	 */
	void clear();

	/**
	 * 元素的数量
	 * @return
	 */
	int size();

	/**
	 * 是否为空
	 * @return
	 */
	boolean isEmpty();

	/**
	 * 是否包含某个元素
	 * @param element
	 * @return
	 */
	boolean contains(E element);

	/**
	 * 添加元素到尾部
	 * @param element
	 */
	void add(E element);

	/**
	 * 获取index位置的元素
	 * @param index
	 * @return
	 */
	E get(int index);

	/**
	 * 设置index位置的元素
	 * @param index
	 * @param element
	 * @return 原来的元素?
	 */
	E set(int index, E element);

	/**
	 * 在index位置插入一个元素
	 * @param index
	 * @param element
	 */
	void add(int index, E element);

	/**
	 * 删除index位置的元素
	 * @param index
	 * @return
	 */
	E remove(int index);

	/**
	 * 查看元素的索引
	 * @param element
	 * @return
	 */
	int indexOf(E element);
}

2.4.3 LinkedList.java

package com.mj;

import com.mj.AbstractList;

public class LinkedList<E> extends AbstractList<E> {
	private Node<E> first;
	private Node<E> last;
	
	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();
		}
	}

	@Override
	public void clear() {
		size = 0;
		first = null;
		last = null;
	}

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

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

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

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

	@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;
	}
	
	/**
	 * 获取index位置对应的节点对象
	 * @param index
	 * @return
	 */
	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 String toString() {
		StringBuilder string = new StringBuilder();
		string.append("size=").append(size).append(", [");
		Node<E> node = first;
		for (int i = 0; i < size; i++) {
			if (i != 0) {
				string.append(", ");
			}
			
			string.append(node);
			
			node = node.next;
		}
		string.append("]");
		return string.toString();
	}
}

2.4.4 ArrayList.java

package com.mj;

@SuppressWarnings("unchecked")
public class ArrayList<E> extends AbstractList<E> {
	/**
	 * 所有的元素
	 */
	private E[] elements;
	private static final int DEFAULT_CAPACITY = 10;
	
	public ArrayList(int capaticy) {
		capaticy = (capaticy < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capaticy;
		elements = (E[]) new Object[capaticy];
	}
	
	public ArrayList() {
		this(DEFAULT_CAPACITY);
	}
	
	/**
	 * 清除所有元素
	 */
	public void clear() {
		for (int i = 0; i < size; i++) {
			elements[i] = null;
		}
		size = 0;
	}

	/**
	 * 获取index位置的元素
	 * @param index
	 * @return
	 */
	public E get(int index) { // O(1)
		rangeCheck(index);
		
		return elements[index]; 
	}

	/**
	 * 设置index位置的元素
	 * @param index
	 * @param element
	 * @return 原来的元素?
	 */
	public E set(int index, E element) { // O(1)
		rangeCheck(index);
		
		E old = elements[index];
		elements[index] = element;
		return old;
	}

	/**
	 * 在index位置插入一个元素
	 * @param index
	 * @param element
	 */
	public void add(int index, E element) { 
		/*
		 * 最好：O(1)
		 * 最坏：O(n)
		 * 平均：O(n)
		 */
		rangeCheckForAdd(index);
		
		ensureCapacity(size + 1);
		
		for (int i = size; i > index; i--) {
			elements[i] = elements[i - 1];
		}
		elements[index] = element;
		size++;
	} // size是数据规模

	/**
	 * 删除index位置的元素
	 * @param index
	 * @return
	 */
	public E remove(int index) {
		/*
		 * 最好：O(1)
		 * 最坏：O(n)
		 * 平均：O(n)
		 */
		rangeCheck(index);
		
		E old = elements[index];
		for (int i = index + 1; i < size; i++) {
			elements[i - 1] = elements[i];
		}
		elements[--size] = null;
		return old;
	}

	/**
	 * 查看元素的索引
	 * @param element
	 * @return
	 */
	public int indexOf(E element) {
		if (element == null) {
			for (int i = 0; i < size; i++) {
				if (elements[i] == null) return i;
			}
		} else {
			for (int i = 0; i < size; i++) {
				if (element.equals(elements[i])) return i;
			}
		}
		return ELEMENT_NOT_FOUND;
	}
	
	/**
	 * 保证要有capacity的容量
	 * @param capacity
	 */
	private void ensureCapacity(int capacity) {
		int oldCapacity = elements.length;
		if (oldCapacity >= capacity) return;
		
		// 新容量为旧容量的1.5倍
		int newCapacity = oldCapacity + (oldCapacity >> 1);
		E[] newElements = (E[]) new Object[newCapacity];
		for (int i = 0; i < size; i++) {
			newElements[i] = elements[i];
		}
		elements = newElements;
		
		System.out.println(oldCapacity + "扩容为" + newCapacity);
	}
	
	@Override
	public String toString() {
		// size=3, [99, 88, 77]
		StringBuilder string = new StringBuilder();
		string.append("size=").append(size).append(", [");
		for (int i = 0; i < size; i++) {
			if (i != 0) {
				string.append(", ");
			}
			
			string.append(elements[i]);
			
//			if (i != size - 1) {
//				string.append(", ");
//			}
		}
		string.append("]");
		return string.toString();
	}
}

2.4.5 ArrayList2.java

package com.mj;

@SuppressWarnings("unchecked")

/**
 * 有动态缩容操作
 * @author MJ Lee
 *
 * @param <E>
 */
public class ArrayList2<E> extends AbstractList<E> {
	/**
	 * 所有的元素
	 */
	private E[] elements;
	private static final int DEFAULT_CAPACITY = 10;
	
	public ArrayList2(int capaticy) {
		capaticy = (capaticy < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capaticy;
		elements = (E[]) new Object[capaticy];
	}
	
	public ArrayList2() {
		this(DEFAULT_CAPACITY);
	}
	
	/**
	 * 清除所有元素
	 */
	public void clear() {
		for (int i = 0; i < size; i++) {
			elements[i] = null;
		}
		size = 0;
		
		// 仅供参考
		if (elements != null && elements.length > DEFAULT_CAPACITY) {
			elements = (E[]) new Object[DEFAULT_CAPACITY];
		}
	}

	/**
	 * 获取index位置的元素
	 * @param index
	 * @return
	 */
	public E get(int index) { // O(1)
		rangeCheck(index);
		
		return elements[index]; 
	}

	/**
	 * 设置index位置的元素
	 * @param index
	 * @param element
	 * @return 原来的元素?
	 */
	public E set(int index, E element) { // O(1)
		rangeCheck(index);
		
		E old = elements[index];
		elements[index] = element;
		return old;
	}

	/**
	 * 在index位置插入一个元素
	 * @param index
	 * @param element
	 */
	public void add(int index, E element) { 
		/*
		 * 最好：O(1)
		 * 最坏：O(n)
		 * 平均：O(n)
		 */
		rangeCheckForAdd(index);
		
		ensureCapacity(size + 1);
		
		for (int i = size; i > index; i--) {
			elements[i] = elements[i - 1];
		}
		elements[index] = element;
		size++;
	} // size是数据规模

	/**
	 * 删除index位置的元素
	 * @param index
	 * @return
	 */
	public E remove(int index) {
		/*
		 * 最好：O(1)
		 * 最坏：O(n)
		 * 平均：O(n)
		 */
		rangeCheck(index);
		
		E old = elements[index];
		for (int i = index + 1; i < size; i++) {
			elements[i - 1] = elements[i];
		}
		elements[--size] = null;
		
		trim();
		
		return old;
	}

	/**
	 * 查看元素的索引
	 * @param element
	 * @return
	 */
	public int indexOf(E element) {
		if (element == null) {
			for (int i = 0; i < size; i++) {
				if (elements[i] == null) return i;
			}
		} else {
			for (int i = 0; i < size; i++) {
				if (element.equals(elements[i])) return i;
			}
		}
		return ELEMENT_NOT_FOUND;
	}
	
	/**
	 * 保证要有capacity的容量
	 * @param capacity
	 */
	private void ensureCapacity(int capacity) {
		int oldCapacity = elements.length;
		if (oldCapacity >= capacity) return;
		
		// 新容量为旧容量的1.5倍
		int newCapacity = oldCapacity + (oldCapacity >> 1);
		
		// 新容量为旧容量的2倍
		// int newCapacity = oldCapacity << 1;
		E[] newElements = (E[]) new Object[newCapacity];
		for (int i = 0; i < size; i++) {
			newElements[i] = elements[i];
		}
		elements = newElements;
		
		System.out.println(oldCapacity + "扩容为" + newCapacity);
	}
	
	private void trim() {
		// 30
		int oldCapacity = elements.length;
		// 15
		int newCapacity = oldCapacity >> 1;
		if (size > (newCapacity) || oldCapacity <= DEFAULT_CAPACITY) return;
		
		// 剩余空间还很多
		E[] newElements = (E[]) new Object[newCapacity];
		for (int i = 0; i < size; i++) {
			newElements[i] = elements[i];
		}
		elements = newElements;
		
		System.out.println(oldCapacity + "缩容为" + newCapacity);
	}
	
	@Override
	public String toString() {
		// size=3, [99, 88, 77]
		StringBuilder string = new StringBuilder();
		string.append("size=").append(size).append(", [");
		for (int i = 0; i < size; i++) {
			if (i != 0) {
				string.append(", ");
			}
			
			string.append(elements[i]);
			
//			if (i != size - 1) {
//				string.append(", ");
//			}
		}
		string.append("]");
		return string.toString();
	}
}

2.4.6 Asserts.java

package com.mj;

public class Asserts {
	public static void test(boolean value) {
		try {
			if (!value) throw new Exception("测试未通过");
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
}

2.4.7 Main.java

package com.mj;

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]

		Asserts.test(list.indexOf(44) == 3);
		Asserts.test(list.indexOf(22) == List.ELEMENT_NOT_FOUND);
		Asserts.test(list.contains(33));
		Asserts.test(list.get(0) == 11);
		Asserts.test(list.get(1) == 66);
		Asserts.test(list.get(list.size() - 1) == 44);
		
		System.out.println(list);
	}
	
	static void josephus() {
		CircleLinkedList<Integer> list = new CircleLinkedList<>();
		for (int i = 1; i <= 8; i++) {
			list.add(i);
		}
		
		// 指向头结点（指向1）
		list.reset();
		
		while (!list.isEmpty()) {
			list.next();
			list.next();
			System.out.println(list.remove());
		}
	}

	public static void main(String[] args) {
		josephus();
		
//		testList(new ArrayList<>());
//		testList(new LinkedList<>());
		
		
		// testList(new SingleCircleLinkedList<>());
		
		// testList(new CircleLinkedList<>());
		
		/*
		 * gc root对象
		 * 1> 被局部变量指向的对象
		 */
	}
}