数据结构 | 简单实现线性表---数组、单链表、双链表(Java描述)

何谓线性表？

• 逻辑结构：线性表时具有相同特性数据元素的有限序列
  1. 相同特性：把同一类事物归类，方便批量处理
  2. 有限序列：元素个数有限大，表中元素排一列，体现了一对一的逻辑特性(每个元素有且仅有一个前驱和一个后继)
• 存储结构：
  1. 顺序存储结构：（数组）相邻数据元素的存放地址相邻；内存中可用存储单元的地址必须是连续的。
     ① 增删不方便
     ② 改查运用索引较方便
     ③ 若线性表的长度变化不大，且其主要操作是查找，则采用顺序表
  2. 链式存储结构：（链表）相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点数据值，另一部分存放表示结点间关系的指针(前驱/后继)
     ① 增删较方便
     ② 改查不方便
     ③ 若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表

代码展示

简单线性表接口

import java.util.Iterator;
/**
 * 线性表(列表)接口的定义
 * 
 * @author LRRacac
 * 
 */

// MyList接口(使用了泛型，并且继承了迭代器方便迭代数据元素)
public interface MyList<T> extends Iterator<T> {

	// 新增一个元素
	void add(T element);

	// 删除指定内容的元素
	void delete(T element);

	// 删除指定索引的元素
	void delete(int index);

	// 将指定位置的元素替换成新元素
	void update(int index, T newElement);

	// 判断当前列表中是否含有target这个元素
	boolean contains(T target);

	// 返回指定元素的索引值
	int getIndex(T element);

	// 返回指定索引值的元素
	T getValue(int index);
}

数组实现

/**
 * 用顺序存储方式实现列表(数组)
 * 
 * @author LRRacac
 * 
 */
public class MyArrayList<T> implements MyList<T> {

	// 定义数组:真正存储元素的底层结构
	private T[] elements;
	// 定义数组的元素个数,并初始化为0
	private int size = 0;
	// 定义数组的容量,并初始化为10
	private int capacity = 10;
	// 定义迭代器的指针位置
	private int index = 0;

	// 用户设定数组容量
	public MyArrayList(int capacity) {
		this.capacity = capacity;
		elements = (T[]) new Object[capacity];
	}

	// 使用默认数组容量
	public MyArrayList() {
		elements = (T[]) new Object[capacity];
	}

	@Override
	/**
	 * 数组增加元素操作
	 */
	public void add(T element) {
		// 扩容操作：数组长度一旦定义则不可改变，若所需存储元素大于数组容量，则需要重新开辟较大新数组
		if (size == capacity) {
			// 扩容两倍
			capacity *= 2;
			T[] newArr = (T[]) new Object[capacity];
			// 将原来的元素复制到新数组
			for (int i = 0; i < size; i++) {
				newArr[i] = elements[i];
			}
			// 覆盖原数组
			elements = newArr;
		}
		// 添加元素element于位置size；同时注意size本身也会增加
		elements[size++] = element;
	}

	@Override
	/**
	 * 数组删除指定元素值的元素
	 */
	public void delete(T element) {
		// 运用下方自己写的getIndex(T element)方法获取指定元素的索引
		int index = getIndex(element);
		// 调用下方自己写的delete(int index)方法删除元素
		delete(index);
	}

	@Override
	/**
	 * 数组删除指定索引的元素
	 */
	public void delete(int index) {
		// 判断索引是否有效
		if (index < 0 || index > size - 1) {
			return;
		}
		// 创建一个新数组用于存放删除指定元素后的数组
		T[] newArr = (T[]) new Object[capacity];
		for (int i = 0; i < size - 1; i++) {
			if (i < index) {
				// 将待删元素索引之前的所有元素还是原来的位置不变，所以一一赋值给newArr
				newArr[i] = elements[i];
			} else {
				// 而待删元素索引之后的元素一一前移一位
				newArr[i] = elements[i + 1];
			}
		}
		// 用新数组newArr取代原数组elements
		elements = newArr;
		// 注意：删除一个元素后size要-1
		size--;
	}

	@Override
	/**
	 * 数组更改指定索引位置的元素值
	 */
	public void update(int index, T newElement) {
		if (index < 0 || index > size - 1) {
			return;
		}
		// 将原数组中对应index的元素改为newElement
		elements[index] = newElement;
	}

	@Override
	/**
	 * 判断数组中是否含有某元素值
	 */
	public boolean contains(T target) {
		// 调用了下方的getIndex(T element)方法此方法返回对应元素的索引，如果索引为-1则说明数组中不含该元素
		// 而数组中正常索引>0
		return getIndex(target) >= 0;
	}

	@Override
	/**
	 * 获取某元素第一次出现的索引值,若数组不含有该元素则返回-1
	 */
	public int getIndex(T element) {
		// 遍历数组中的元素，判断是否等于element
		// 是则返回对应的索引值，否则返回-1
		for (int i = 0; i < size; i++) {
			if (elements[i].equals(element)) {
				return i;
			}
		}
		return -1;
	}

	@Override
	/**
	 * 获取指定索引的元素值,如果没有则返回null
	 */
	public T getValue(int index) {
		if (index < 0 || index > size - 1) {
			return null;
		}
		// 数组可以直接返回指定索引的元素值
		return elements[index];
	}

	@Override
	/**
	 * 重写toString()方法，用于输出数组
	 */
	public String toString() {
		StringBuilder sb = new StringBuilder("[");
		for (int i = 0; i < size; i++) {
			sb.append(elements[i] + (i == size - 1 ? "" : " , "));
		}
		sb.append("]");
		return sb.toString();
	}

	@Override
	/**
	 * 重写迭代器hasNext()方法，判断后面是否还有元素，用于迭代器输出数组
	 */
	public boolean hasNext() {
		int i = index;
		i++;
		return i <= size;
	}

	@Override
	/**
	 * 重写迭代器next()方法，获取下一个元素，用于迭代器输出数组
	 */
	public T next() {
		while (hasNext()) {
			return elements[index++];
		}
		return null;
	}
}

链表节点设计

/**
 * 链表的结点的定义
 * 
 * @author LRRacac
 *
 */
public class ListNode {
	// 结点的数据
	Object data;
	// 结点的前驱
	ListNode pre;
	// 结点的后继
	ListNode next;

	// 构造方法，用于初始化结点
	public ListNode(Object data) {
		this.data = data;
	}
}

单链表实现

/**
 * 用链表存储方式实现列表(单链表)
 * 
 * @author LRRacac
 *
 */
public class SingleLinkedList<T> implements MyList<T> {
	// 定义单链表第一个元素
	private ListNode first;
	// 定义单链表最后一个元素
	private ListNode last;
	// 定义单链表元素个数
	private int size;
	// 定义迭代器指针
	private ListNode now;

	@Override
	/**
	 * 单链表增加元素操作
	 */
	public void add(T element) {
		// 当第一个元素不存在时，创建第一个元素(此时第一个元素即是最后一个元素)
		if (first == null) {
			first = new ListNode(element);
			last = first;
			now = first;
		} else { // 将单链表最后一个元素的next指向新创建元素，同时改变最后一个元素为新创建元素
			last.next = new ListNode(element);
			last = last.next;
		}
		// 使用size记录单链表中元素个数
		size++;
	}

	@Override
	/**
	 * 单链表实现删除指定元素值的第一个元素
	 */
	public void delete(T element) {
		// 定义标记结点p
		ListNode p = first;
		// 标记结点的前一个结点pre
		ListNode pre = null;
		// 循环遍历所有元素，直到找到与目标元素相同的元素
		while (p != null) {
			if (p.data.equals(element)) {
				// 当目标元素为第一个元素时，将first指向第二个元素
				if (p == first) {
					first = first.next;
				} else { // 否则，将目标元素的前一个元素指向目标元素的后一个元素
					pre.next = p.next;
				}
				// 注意：删除元素后需将size-1
				size--;
				break;
			}
			// 此轮没有找到目标元素，则两指针后移
			pre = p;
			p = p.next;
		}
	}

	@Override
	/**
	 * 单链表实现删除指定索引位置的元素
	 */
	public void delete(int index) {
		// 判断index的合法性
		if (index < 0 || index > size - 1) {
			return;
		}
		// 定义标记结点p
		ListNode p = first;
		// 定义标记结点的前驱pre
		ListNode pre = null;
		// i表示指针指向位置的索引
		for (int i = 0; i < size; i++) {
			if (i == index) {
				if (i == 0) {
					// 当待删除的元素为第一个元素时，直接将first改为第二个元素
					first = first.next;
				} else {
					// 否则，将待删结点p的前驱pre的后继跳过待删结点p，直接指向待删结点的后继
					pre.next = p.next;
				}
				// 注意：删除元素后需将size-1
				size--;
				break;
			}
			// 此轮没有找到目标元素，则两指针后移
			pre = p;
			p = p.next;
		}
	}

	@Override
	/**
	 * 单链表实现更改某个索引位置的元素值
	 */
	public void update(int index, T newElement) {
		if (index < 0 || index > size - 1) {
			return;
		}
		// 定义标记结点p
		ListNode p = first;
		for (int i = 0; i < size; i++) {
			// 遍历结点，直到索引为index
			if (i == index) {
				// 将对应索引位置的结点数据改为newElement
				p.data = newElement;
				break;
			}
			// 指针后移
			p = p.next;
		}
	}

	@Override
	/**
	 * 单链表实现判断列表中是否含有某值
	 */
	public boolean contains(T target) {
		// 定义标记结点p
		ListNode p = first;
		// 遍历结点寻找是否存在结点与目标值target相等
		while (p != null) {
			if (p.data.equals(target)) {
				return true;
			}
			// 指针后移
			p = p.next;
		}
		return false;
	}

	@Override
	/**
	 * 单链表实现获取某个元素的索引值,如果不存在则返回-1
	 */
	public int getIndex(T element) {
		// 定义标记结点p
		ListNode p = first;
		// 定义索引
		int i = 0;
		// 循环遍历
		while (p != null) {
			// 直到数据等于element，返回索引值
			if (p.data.equals(element)) {
				return i;
			}
			// 指针后移
			p = p.next;
			// 索引自增
			i++;
		}
		return -1;
	}

	@Override
	/**
	 * 单链表实现获取某索引位置的元素值
	 */
	public T getValue(int index) {
		if (index < 0 || index > size - 1) {
			return null;
		}
		ListNode p = first;
		int i = 0;
		while (p != null) {
			if (i == index) {
				return (T) p.data;
			}
			p = p.next;
			i++;
		}
		return null;
	}

	@Override
	/**
	 * 重写toString()方法，用于输出单链表
	 */
	public String toString() {
		StringBuilder sb = new StringBuilder("[");
		ListNode p = first;
		while (p != null) {
			sb.append(p.data);
			if (p.next != null) {
				sb.append(" , ");
			}
			p = p.next;
		}
		return sb.append("]").toString();
	}

	/**
	 * 迭代器
	 */
	@Override
	public boolean hasNext() {
		return now != null;
	}

	/**
	 * 重写迭代器next()方法
	 */
	@Override
	public T next() {
		ListNode next = now;
		now = now.next;
		return (T) next.data;
	}
}

双链表实现

/**
 * 用链表存储方式实现列表(双链表)
 * 
 * @author LRRacac
 *
 */

public class DoubleLinkedList<T> implements MyList<T> {
	// 定义双链表第一个元素(哑元)
	private ListNode first = new ListNode(null);
	// 定义双链表最后一个元素(哑元)
	private ListNode last = new ListNode(null);
	// 定义双链表元素个数
	private int size;
	// 定义迭代器指针
	private ListNode now = first;

	// 构造器加载初始首尾哑元的指针指向
	public DoubleLinkedList() {
		first.next = last;
		last.pre = first;
	}

	@Override
	/**
	 * 双链表增加元素操作
	 */
	public void add(T element) {
		ListNode newNode = new ListNode(element);
		// 双链表添加元素需要维护4条指针
		// 将末尾哑元的前驱的后继改为新增结点newNode
		last.pre.next = newNode;
		// 将新增结点的前驱改为末尾哑元的前驱
		newNode.pre = last.pre;
		// 将末尾哑元的前驱改为新增结点
		last.pre = newNode;
		// 将新增结点的后继改为末尾哑元
		newNode.next = last;
		// 注意：新增元素后size+1
		size++;
	}

	@Override
	/**
	 * 双链表实现删除指定元素值的第一个元素
	 */
	public void delete(T element) {
		// 定义标记结点p
		ListNode p = first.next;
		// 循环遍历所有元素，直到找到与目标元素相同的元素
		while (p != last) {
			if (p.data.equals(element)) {
				// 将待删结点p的前驱的后继改为待删结点p的后继
				p.pre.next = p.next;
				// 将待删结点p的后继的前驱改为待删结点p的前驱
				p.next.pre = p.pre;
				// 删除待删结点p的指向
				p.next = null;
				p.pre = null;
				size--;
				break;
			}
			// 此轮没有找到目标元素，则指针后移
			p = p.next;
		}
	}

	@Override
	/**
	 * 双链表实现删除指定索引位置的元素
	 */
	public void delete(int index) {
		// 判断index是否合法
		if (index < 0 || index > size - 1) {
			return;
		}
		ListNode p = first.next;
		// i表示指针指向位置的索引
		for (int i = 0; i < size; i++) {
			if (i == index) {
				p.pre.next = p.next;
				p.next.pre = p.pre;
				p.pre = null;
				p.next = null;
				size--;
				break;
			}
			p = p.next;
		}
	}

	@Override
	/**
	 * 双链表实现更改某个索引位置的元素值
	 */
	public void update(int index, T newElement) {
		if (index < 0 || index > size - 1) {
			return;
		}
		ListNode p = first.next;
		for (int i = 0; i < size; i++) {
			if (i == index) {
				p.data = newElement;
				break;
			}
			p = p.next;
		}
	}

	@Override
	/**
	 * 双链表实现判断列表中是否含有某值
	 */
	public boolean contains(T target) {
		ListNode p = first.next;
		while (p != last) {
			if (p.data.equals(target)) {
				return true;
			}
			p = p.next;
		}
		return false;
	}

	@Override
	/**
	 * 双链表实现获取某个元素的索引值,如果不存在则返回-1
	 */
	public int getIndex(T element) {
		ListNode p = first.next;
		int i = 0;
		while (p != last) {
			if (p.data.equals(element)) {
				return i;
			}
			p = p.next;
			i++;
		}
		return -1;
	}

	@Override
	/**
	 * 双链表实现获取某索引位置的元素值
	 */
	public T getValue(int index) {
		if (index < 0 || index > size - 1) {
			return null;
		}
		ListNode p = first.next;
		int i = 0;
		while (p != last) {
			if (i == index) {
				return (T) p.data;
			}
			p = p.next;
			i++;
		}
		return null;
	}

	@Override
	/**
	 * 重写toString()方法，用于输出链表
	 */
	public String toString() {
		StringBuilder sb = new StringBuilder("[");
		ListNode p = first.next;
		while (p != last) {
			sb.append(p.data);
			if (p.next != last) {
				sb.append(" , ");
			}
			p = p.next;
		}
		return sb.append("]").toString();
	}

	/**
	 * 重写迭代器hasNext()方法
	 */
	@Override
	public boolean hasNext() {
		return now.next != last;
	}

	/**
	 * 重写迭代器next()方法
	 */
	@Override
	public T next() {
		now = now.next;
		return (T) now.data;
	}
}

测试代码

/**
 * 测试代码
 * 
 * @author LRRacac
 *
 */
public class Test {
	public static void main(String[] args) {
		// 测试线性表-顺序存储-数组
		// 创建MyArrayList数组对象，并且将泛型设置为String类型--以保证list里的所有元素均为String类型(根据自己的需要也可以设为别的类型)
		MyArrayList<String> list = new MyArrayList<>();
		// 数组添加元素
		list.add("I");
		list.add("love");
		list.add("Java");
		list.add("1");
		list.add("2");
		list.add("3");
		// toString()输出数组
		System.out.println(list);
		// 迭代器输出数组
		while (list.hasNext()) {
			System.out.println(list.next());
		}
		// 数组的其他方法自己试试，笔者准备偷懒

		// 测试线性表-单链表
		SingleLinkedList<Integer> list1 = new SingleLinkedList<>();
		// 单链表添加元素
		list1.add(11);
		list1.add(22);
		list1.add(33);
		list1.add(44);
		list1.add(55);
		System.out.println(list1);
		// 单链表实现删除元素
		list1.delete(1);
		System.out.println(list1);
		// 单链表实现删除指定元素
		list1.delete(Integer.valueOf(33));
		System.out.println(list1);
		// 单链表实现更改某个索引位置的元素值
		list1.update(0, Integer.valueOf(66));
		System.out.println(list1);
		// 单链表实现判断列表中是否含有某值
		System.out.println(list1.contains(Integer.valueOf(44)));
		// 单链表实现获取某个元素的索引值,如果不存在则返回-1
		System.out.println(list1.getIndex(Integer.valueOf(44)));
		// 单链表实现获取某索引位置的元素值
		System.out.println(list1.getValue(2));

		// 双链表自己实现哈
	}
}

骚话时刻：
想做一个链表，灵活多变，不像数组那么死板(出生就限定了长度)
虽不能决定自己的出生，但是可以通过灵活地add技能、delete缺点等等来应对这复杂多变的世界

正值新冠病毒多发时期，只能通过 “宅” 来保护自己、爱护他人、“报效祖国”
多希自己是个小学生，单纯又无知，一定会好好享受这突如其来的延长版假期
现在的我刷刷微博会因为各种喷子而气恼、关心时事却因为自己无能为力而气馁、每每无心学习却又愧疚无比，这时代哇，连玩都不能玩痛快了，毕竟欠下的学习债总要还的(呸呸呸，太丧了，别学我)
思来想去
还是静下心来学习技术 码码代码比较自在
觉得某伟老师说的一句话很在理：地球上资源就那么多，新一代一定会比老一代更加辛苦
虽然笔者已经正式加入21考研大军 但更博一定不会断(希望不要打脸)
中国加油，武汉挺住，keep moving！
康康下图涨姿势咯~