链表
链式存储结构
定义
线性表的链式存储结构的特点是用一组任意的存储单元的存储线性表的数据元素，这组存储单元是可以连续的，也可以是不连续的。
种类
结构图单链表 应用：MessageQueue插入 enqueueMessage(Message msg,Long when)。删除 next ()。单循环链表双链表 LinkedList双向循环链表
优缺点
优点：插入删除快
缺点：不支持随即访问
学习例子
基于系统 API LinkedList 将麻将进行分组排序
思想
逻辑步骤
把所有的点数分别装入到对应的链表组中在把链表中所有的点数合并在一起在把所有的的点数分别装在对应的链表中最后把对应的点数链表装在一个新的集合中
代码编写
/*** 麻将数据 Bean*/public class Mahjong {public int suit;//筒，万，索public int rank;//点数 一 二 三public Mahjong(int suit, int rank) {this.suit = suit;this.rank = rank;}@Overridepublic String toString() {return "("+this.suit+" "+this.rank+")";}}复制代码
/*** 用系统自带的 链表结构 LinkedList 来进行将麻将排序* @param list*/private void radixSort(LinkedList<Mahjong> list) {//1. 先把所有的点数分别装入到对应的链表组中//创建一个点数最大的为 9 的集合LinkedList[] linkedList = new LinkedList[9];//先初始化这 9 个链表目的是装所有的对应的点数for (int i = 0; i < 9; i++) {linkedList[i] = new LinkedList();}while (list.size() > 0) {//取出对应的元素放入到链表中Mahjong mahjong = list.remove();//mahjong.rank - 1 的意思就是对应的集合下标linkedList[mahjong.rank - 1].add(mahjong);}//2. 然后再把所有的链表中的点数合并在一起for (int i = 0; i < linkedList.length; i++) {list.addAll(linkedList[i]);}//3. 在把所有的点数分别装入到对应的链表中//花色有 3 个，那么我们就创建 3 个链表来代表装入对应的花色LinkedList[] linkedLists =new LinkedList[3];for (int i = 0; i < 3; i++) {linkedLists[i] = new LinkedList();}//把对应的花色装在对应的链表中while (list.size()>0){Mahjong mahjong = list.remove();linkedLists[mahjong.suit - 1].add(mahjong);}//4. 最后在把对应的点数链表装在一个新的集合中for (int i = 0; i < linkedLists.length; i++) {list.addAll(linkedLists[i]);}}复制代码
应用
数据量几十个,插入操作多的情况
编写双向链表 LinkedList CURD
参考图解
编写代码
/*** Created by yangk on /1/29.* <p>* 自己定义的双向链表结构 LinkedList*/public class CustomLinkedList<E> {/*** 链表的头部*/transient Node<E> head;/*** 链表的尾部*/transient Node<E> tail;/*** 当前链表的大小*/transient int size;/*** 存入数据*/public boolean add(E e) {linkLast(e);return true;}/*** 返回当前链表的大小** @return*/public int getSize() {return size;}/*** 将当前数据存入到链表的头部** @param e*/public void addFirst(E e) {Node<E> h = head;//创建新节点Node<E> newNode = new Node<>(null, e, head);head = newNode;if (head == null) {tail = newNode;} else {h.pre = newNode;}size++;}/*** 根据索引搜索到的节点数据** @param index*/public E get(int index) {if (isPositionIndex(index)) {return searchNode(index).data;}return null;}/*** 根据索引添加数据** @param index* @param e*/public void add(int index, E e) {addIndex(index, e);}/*** 删除第一个节点*/public E remove() {return removeFirst();}/*** 删除头节点** @return*/private E removeFirst() {Node<E> h = head;if (h == null)throw new NoSuchElementException();return unlinkFirst(h);}private E unlinkFirst(Node<E> h) {//删除的 数据E deleData = h.data;//找到要删除的后驱Node next = h.next;//清理节点h.data = null;h.next = null;//将当前要删除的后驱置为链表头head = next;if (next == null) {tail = null;} else {next.pre = null;}h = null;size--;return deleData;}private void addIndex(int index, E e) {if (isPositionIndex(index)) {//找到当前需要插入的索引位置if (index == size) {linkLast(e);} else {add(e, searchNode(index));}}}/*** 添加新节点到 searchNode 前驱** @param e* @param searchNode*/private void add(E e, Node<E> searchNode) {//找到 searchNode 前驱节点Node<E> snPre = searchNode.pre;//创建新节点Node<E> newNode = new Node<>(snPre, e, searchNode);searchNode.pre = newNode;//这里判断 snPre 是否为空 入股为空说明 head 没有数据，如果有数据 就直接把 snPre . next() = newNodeif (snPre == null) {head = newNode;} else {snPre.next = newNode;}size++;}private Node<E> searchNode(int index) {//优化寻找节点 如果 index > size / 2 就从尾部开始查询，反之从 head 开始遍历查询if (index > (size >> 1)) {Node<E> t = tail;for (int i = size - 1; i > index; i--) {t = t.pre;}return t;} else {Node<E> h = head;for (int i = 0; i < index; i++) {h = h.next;}return h;}}/*** 将数据存入到当前链表尾部** @param e*/private void linkLast(E e) {//拿到尾部的节点数据Node<E> t = tail;//创建新的节点数据,因为是存在当前节点的尾部，// 那么直接默认将当前添加进来的 E 的前驱设置为// 当前链表中的尾部数据，现在已经形成单链表了// 下一步直接形成双向链表Node<E> newNode = new Node<>(t, e, null);//现在是双向链表，要把新的节点指向当前的尾部节点，尾部节点指向新的节点tail = newNode;//如果尾部节点为空 那么说明 head 也是空数据 那就吧新节点数据赋值给 headif (t == null) {head = newNode;} else {t.next = newNode;}size++;}/*** 创建一个空的构造者*/public CustomLinkedList() {}private boolean isPositionIndex(int index) {return index >= 0 && index <= size;}/*** 定义一个内部节点* <p>* 双向链表需要前驱，后驱，数据*/public static class Node<E> {/*** 当前节点的前驱*/private Node pre;/*** 当前节点的数据*/private E data;/*** 当前节点的后驱*/private Node next;public Node(Node pre, E data, Node last) {this.pre = pre;this.data = data;this.next = last;}}}复制代码
测试代码
@Testpublic void testCustomLinkedList() {CustomLinkedList<Integer> linkedList = new CustomLinkedList<Integer>();linkedList.add(22);linkedList.add(2);linkedList.add(77);linkedList.add(6);linkedList.add(43);linkedList.add(76);linkedList.add(89);linkedList.add(0,0);for (int i = 0; i < linkedList.size; i++) {int integer = linkedList.get(i);System.out.println("--CustomLinkedList--CustomLinkedList" +integer+"");}System.out.println("\n\n");Integer remove = linkedList.remove();System.out.println("--CustomLinkedList--CustomLinkedList" +remove);Integer remove1 = linkedList.remove();System.out.println("--CustomLinkedList--CustomLinkedList" +remove1+"");Integer remove2 = linkedList.remove();System.out.println("--CustomLinkedList--CustomLinkedList" + remove2 + "");System.out.println("\n\n");for (int i = 0; i < linkedList.size; i++) {int integer = linkedList.get(i);System.out.println("--CustomLinkedList--CustomLinkedList" +integer+"");}}复制代码
测试结果
编写简单的 ArrayList CURD
public class CustomArrayList<E> {/*** 默认的空元素对象*/private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};/*** 空元素数据*/private static final Object[] EMPTY_ELEMENTDATA = {};/*** 默认的元素对象*/private Object[] elementData = null;/*** 容量大小*/private int size = 0;/*** 默认的容量大小*/private static final int DEFAULT_CAPACITY = 10;/*** 最大的数量** TODO------------减 8 是什么意思没有搞懂*/private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;/*** 赋值为一个空对象*/public CustomArrayList(){elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}/*** 外部指定初始化一个容量大小* @param initCapacity*/public CustomArrayList(int initCapacity){if (initCapacity > 0){elementData = new Object[initCapacity];}else if (initCapacity == 0){elementData = EMPTY_ELEMENTDATA;}else {throw new IllegalArgumentException("Illegal Capacity: "+initCapacity);}}/*** 添加数据*/public boolean add(E e){//判断是否需要开辟容量空间checkIsNeedCapacity(size + 1);//添加添加数据elementData[size++] = e;return true;}private void checkIsNeedCapacity(int minCapacity) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA){minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);}ensureExplicitCapacity(minCapacity);}private void ensureExplicitCapacity(int minCapacity) {// overflow-conscious codeif (minCapacity - elementData.length > 0)grow(minCapacity);}/*** 开辟空间的核心代码* @param minCapacity*/private void grow(int minCapacity) {// overflow-conscious codeint oldCapacity = elementData.length;int newCapacity = oldCapacity + (oldCapacity >> 1);if (newCapacity - minCapacity < 0)newCapacity = minCapacity;if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);// minCapacity is usually close to size, so this is a win:elementData = Arrays.copyOf(elementData, newCapacity);}private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflowthrow new OutOfMemoryError();return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;}}复制代码
编写单向链表结构的 CURD
/*** Created by yangk on /2/19.*/public class SingleLinked<T> {/*** 头节点*/Node<T> head;/*** 链表长度*/int size = 0;/*** 将数据添加到链表中** @param data*/public void add(T data) {Node node = new Node(data);if (head == null) {head = node;return;}Node<T> tmp = head;while (tmp.next != null) {tmp = tmp.next;}tmp.next = node;size++;}/*** 将数据添加到第一个位置** @param data*/public void addHead(T data) {Node node = new Node(data);if (head == null) {head = node;size++;return;}Node n = head;node.next = n;head = node;size++;}public void add(int index, T data) {Node node = new Node(data);if (index == 0) {addHead(data);} else {Node tmp = head;for (int i = 0; i < index - 1; i++) {tmp = tmp.next;}Node n = tmp.next;tmp.next = node;node.next = n;size++;}}/*** 全部清除数据*/public void clear() {head = null;size = 0;}public boolean remove(int index) {//2Node<T> tmp = head;if (index == 0) {Node<T> newHead = tmp.next;head = null;head = newHead;size--;return true;}if (index < size) { // 1 2 3 4 5 6 7 3for (int i = 0; i < index - 2; i++) {tmp = tmp.next;}Node<T> pre = tmp;//要删除的节点Node<T> next = tmp.next;Node<T> p = tmp.next.next;pre.next = p;next = null;size--;return true;}return false;}/*** 节点数据*/private class Node<T> {T data;Node<T> next;public Node(T data, Node<T> next) {this.data = data;this.next = next;}public Node(T next) {this.data = next;}}public void println() {if (head == null) return;Node n = head;while (n != null){System.out.println(n.data + "\n");n = n.next;}}}复制代码
