数据结构和算法2-线性-链
本文共 15044 字，大约阅读时间需要 50 分钟。
数据结构和算法系列共八篇
1.线性表
线性表是n个类型相同数据元素的有限序列。(a0 ,a1…, ax)
线性表特点
- 元素类型是相同的
一个线性表里元素要相同。元素可以int、str、对象等，但同一类型要在一个线性表种。
- 有序
有头有尾，其他元素前后是1:1对应的
- 有限
线性表是有length的。0代表空的
2.逻辑结构
这只是逻辑上的概念，有头有尾，中间一个个紧挨着1:1,是有限的。
比如排队 (只要它们满足线性表的特征即可)
- 一个个前后站位，站的整整齐齐
- 一个个拉着绳子，站的歪歪扭扭
3.存储结构
存储结构分
- 顺序表----顺序存储结构
- 链表----链式存储结构
3-1.顺序表
特点：在内存中分配连续的空间，只存储数据，不需要存储地址信息。位置就隐含着地址。
优点
- 节省存储空间,只存数据,不存地址
- 索引查找效率高，即每一个结点对应一个序号，由该序号可以直接计算出来结点的存储地址。
元素类型定了,位置知道了,那么存储的在内存的位置就很容器确定了(头地址+位置*元素类型大小)
缺点
- 插入和删除(中间的位置元素操作)效率低,因为是连续空间,要移动一些操作
- 按着下标/索引,查询速度快.如果按着值内容查,那么就得全部遍历了
- 空间是必须连续的,得提前分配好空间.(定义了多了,但存的少了,可能导致空闲浪费)
3-2.链表
特点：元素的存储对应的是不连续的存储空间，每个存储结点除了数据外,还要记录自己所在位置(数据域和指针域)。
优点
- 插入、删除灵活 (不必移动节点，只要改变节点中的指针，但是需要先定位到元素上)
- 有元素才会分配结点空间，不会有闲置的结点。
缺点
- 比顺序存储结构的存储密度小 (要存指针域,所以站的空间多了点)。
- 查询慢,要根据已知节点(链头)慢慢找
4.接口
list常见操作方法
public interface IList { // 返回线性表的大小，即数据元素的个数。 public int size(); // 返回线性表中序号为 i 的数据元素 public Object get(int i); // 如果线性表为空返回 true，否则返回 false。 public boolean isEmpty(); // 判断线性表是否包含数据元素 e public boolean contains(Object e); // 返回数据元素 e 在线性表中的序号 public int indexOf(Object e); // 将数据元素 e 插入到线性表中 i 号位置 public void add(int i, Object e); // 将数据元素 e 插入到线性表末尾 public void add(Object e); // 将数据元素 e 插入到元素 obj 之前 public boolean addBefore(Object obj, Object e); // 将数据元素 e 插入到元素 obj 之后 public boolean addAfter(Object obj, Object e); // 删除线性表中序号为 i 的元素,并返回之 public Object remove(int i); // 删除线性表中第一个与 e 相同的元素 public boolean remove(Object e); // 替换线性表中序号为 i 的数据元素为 e，返回原数据元素 public Object replace(int i, Object e);} 5.顺序表实现
实现类
import java.util.Arrays;/** * 顺序表 * * @author: iworkh-沐雨云楼 * @date: 2020-07-01 */public class MyArrayList implements IList { // 底层数组来存储多个元素 private Object[] elementData; // 存储的元素的个数，线性表的长度，(不是数组的长度) // 因为数组长度是会动态扩容，会比数据多,不然每次操作都要扩数组太低效了 private int size; private static final int DEFAULT_INIT_SIZE = 16; public MyArrayList(int initSize) { if(initSize < 0){ throw new RuntimeException("初始长度要大于0："+initSize); } this.elementData = new Object[initSize]; } public MyArrayList() { this(DEFAULT_INIT_SIZE); } @Override public int size() { return this.size; } @Override public Object get(int i) { if (isIndexOutOfBounds(i)) { throw new IndexOutOfBoundsException("数组越界异常：" + i); } return elementData[i]; } @Override public boolean isEmpty() { return this.size == 0; } @Override public boolean contains(Object e) { // 通过indexOf方法返回值来处理 int findIndex = this.indexOf(e); return findIndex > 0; } @Override public int indexOf(Object e) { if (e == null) { for (int i = 0; i < size; i++) { if (elementData[i] == null) { return i; } } } else { for (int i = 0; i < size; i++) { if (e.equals(elementData[i])) { return i; } } } return -1; } @Override public void add(int i, Object e) { // i有没超过size值 if (isIndexOutOfBounds(i)) { throw new IndexOutOfBoundsException("数组越界异常：" + i); } // 需要扩容? if (this.size == this.elementData.length) { grow(); } // i后面数据要移位 // for (int num = this.size; num > i; num--) { // this.elementData[num] = this.elementData[num - 1]; // } if (this.size > i) { System.arraycopy(this.elementData, i, this.elementData, i + 1, this.size - i); } // 插入i位置值 this.elementData[i] = e; this.size++; } private void grow() { // 扩容一倍 this.elementData = Arrays.copyOf(elementData, this.elementData.length * 2); } @Override public void add(Object e) { // 需要扩容? if (this.size == this.elementData.length) { grow(); } this.elementData[size] = e; this.size++; } @Override public boolean addBefore(Object obj, Object e) { if (this.size==this.elementData.length){ grow(); } // 先找到obj的位置 int foundIndex = this.indexOf(obj); // 1,2,3,4,5,6 // 移动obj以及后面的元素 if (this.size > foundIndex) { System.arraycopy(this.elementData, foundIndex, this.elementData, foundIndex + 1, this.size - foundIndex); } // 然后插入e在obj原来位置 this.elementData[foundIndex] = e; // 个数加1 this.size++; return true; } @Override public boolean addAfter(Object obj, Object e) { if (this.size==this.elementData.length){ grow(); } // 先找到obj的位置 int foundIndex = this.indexOf(obj); // 1,2,3,4,5,6 // 移动obj后面的元素 if (this.size > foundIndex) { System.arraycopy(this.elementData, foundIndex + 1, this.elementData, foundIndex + 2, this.size - foundIndex - 1); } // 然后插入e在obj后面 this.elementData[foundIndex + 1] = e; // 个数加1 this.size++; return true; } @Override public Object remove(int i) { if (isIndexOutOfBounds(i)) { throw new IndexOutOfBoundsException("数组越界异常：" + i); } Object oldValue = this.elementData[i]; fastRemove(i); return oldValue; } @Override public boolean remove(Object e) { if (e == null) { for (int index = 0; index < size; index++) { if (elementData[index] == null) { fastRemove(index); return true; } } } else { for (int index = 0; index < size; index++) { if (e.equals(elementData[index])) { fastRemove(index); return true; } } } return false; } private void fastRemove(int index) { int numMoved = size - index - 1; if (numMoved > 0) { System.arraycopy(elementData, index + 1, elementData, index, numMoved); } // clear to let GC do its work elementData[--size] = null; } @Override public Object replace(int i, Object e) { if (isIndexOutOfBounds(i)) { throw new IndexOutOfBoundsException("数组越界异常：" + i); } this.elementData[i] = e; return e; } private boolean isIndexOutOfBounds(int index) { return index < 0 || index > this.size; } @Override public String toString() { // 为了简单，这直接使用Arrays.toString来打印了。(这有null的也打印了) // 其实应该for循环，取出size以内的元素。 return "MyArrayList{" + "elementData=" + Arrays.toString(elementData) + '}'; }} 测试类
public class MyArrayListTest { public static void main(String[] args) { IList list = new MyArrayList(); System.out.println(list.isEmpty()); list.add("a"); System.out.println(list.isEmpty()); list.add("c"); list.add("m"); list.add(1, "b"); System.out.println(list); list.addBefore("m", "l"); System.out.println(list); list.addAfter("c", "h"); System.out.println(list); System.out.println(list.get(2)); System.out.println(list.indexOf("c")); list.replace(2, "B"); System.out.println(list); list.remove(2); System.out.println(list); list.remove("b"); System.out.println(list); }} 6.链表实现
6-1.单链表
节点,有两部分组成(数据和下一个数据)
public class Node { private Object data; private Node next; public Node() { } public Node(Object data, Node next) { this.data = data; this.next = next; } public Object getData() { return data; } public void setData(Object data) { this.data = data; } public Node getNext() { return next; } public void setNext(Node next) { this.next = next; }} 实现类
public class MySingleLinkedList implements IList { private Node head = new Node(); //默认长度是0，头结点不算 public int size; @Override public int size() { return this.size; } public MySingleLinkedList() { } @Override public Object get(int i) { if (isIndexOutOfBounds(i)) { throw new IndexOutOfBoundsException("数组越界异常：" + i); } Node currentNode = this.head.getNext(); for (int num = 0; num < this.size; num++) { if (num == i) { return currentNode.getData(); } else { currentNode = currentNode.getNext(); } } return null; } @Override public boolean isEmpty() { return this.size == 0; } @Override public boolean contains(Object e) { return indexOf(e) > 0; } @Override public int indexOf(Object e) { Node currentNode = this.head.getNext(); for (int num = 0; num < this.size; num++) { Object data = currentNode.getData(); if (data.equals(e)) { return num; } else { currentNode = currentNode.getNext(); } } return -1; } @Override public void add(int i, Object e) { if (isIndexOutOfBounds(i)) { throw new IndexOutOfBoundsException("数组越界异常：" + i); } // preNode指向head，那么preNode的next作为当前元素 // 0代表thead的next元素。所以preNode代表的是前一个元素 Node preNode = this.head; for (int num = 0; num < i; num++) { preNode = preNode.getNext(); } // 将插入的next指向找到的当前元素的下一个 // 将要当前元素的next指向要插入的值 Node currentNextNode = preNode.getNext(); Node insertNode = new Node(e, currentNextNode); preNode.setNext(insertNode); this.size++; } @Override public void add(Object e) { this.add(this.size, e); } @Override public boolean addBefore(Object obj, Object e) { Node preNode = this.head; Node currentNode = preNode.getNext(); for (int num = 0; num < this.size; num++) { // 简单起见, obj为null的情况，就不考虑 if (obj.equals(currentNode.getData())) { // 将插入的next指向找到的当前元素 // 将要前一个的next指向要插入的Node Node insertNode = new Node(e, currentNode); preNode.setNext(insertNode); this.size++; return true; } else { preNode = preNode.getNext(); currentNode = currentNode.getNext(); } } return false; } @Override public boolean addAfter(Object obj, Object e) { Node currentNode = this.head.getNext(); for (int num = 0; num < this.size; num++) { // 简单起见, obj为null的情况，就不考虑 if (obj.equals(currentNode.getData())) { // 将插入的next指向找到的当前元素的下一个 // 将要当前元素的next指向要插入的值 Node oldNextNode = currentNode.getNext(); Node insertNode = new Node(e, oldNextNode); currentNode.setNext(insertNode); this.size++; return true; } else { currentNode = currentNode.getNext(); } } return false; } @Override public Object remove(int i) { if (isIndexOutOfBounds(i)) { throw new IndexOutOfBoundsException("数组越界异常：" + i); } Node preNode = this.head; Node currentNode = preNode.getNext(); for (int num = 0; num < this.size; num++) { // 简单起见, obj为null的情况，就不考虑 if (i == num) { // 将要删node前一个node的next指当删node下个node Object result = currentNode.getData(); preNode.setNext(currentNode.getNext()); this.size--; return result; } else { preNode = preNode.getNext(); currentNode = currentNode.getNext(); } } return null; } @Override public boolean remove(Object e) { Node preNode = this.head; Node currentNode = preNode.getNext(); for (int num = 0; num < this.size; num++) { // 简单起见, obj为null的情况，就不考虑 if (e.equals(currentNode.getData())) { // 将要删node前一个node的next指当删node下个node preNode.setNext(currentNode.getNext()); this.size--; return true; } else { preNode = preNode.getNext(); currentNode = currentNode.getNext(); } } return false; } @Override public Object replace(int i, Object e) { if (isIndexOutOfBounds(i)) { throw new IndexOutOfBoundsException("数组越界异常：" + i); } Node currentNode = this.head.getNext(); for (int num = 0; num < this.size; num++) { if (i == num) { currentNode.setData(e); return e; } else { currentNode = currentNode.getNext(); } } return null; } private boolean isIndexOutOfBounds(int index) { return index < 0 || index > this.size; } @Override public String toString() { StringBuilder builder = new StringBuilder("["); Node p = head.getNext(); while (p != null) { //取出结点值 Object data = p.getData(); //加入StringBuffer builder.append(data + ","); //后移一个结点 p = p.getNext(); } //删除最后的一个逗号 if (builder.length() > 1) { builder.deleteCharAt(builder.length() - 1); } builder.append("]"); return builder.toString(); }} 测试类
public class MySingleLinkedListTest { public static void main(String[] args) { IList list = new MySingleLinkedList(); System.out.println(list.isEmpty()); list.add("a"); System.out.println(list.isEmpty()); list.add("c"); list.add("m"); System.out.println(list); list.add(1, "b"); System.out.println(list); list.addBefore("m", "l"); System.out.println(list); list.addAfter("c", "h"); System.out.println(list); System.out.println(list.get(2)); System.out.println(list.indexOf("c")); list.replace(2, "B"); System.out.println(list); list.remove(2); System.out.println(list); list.remove("b"); System.out.println(list); }} 6-2.双向列表
单链表的一个优点是结构简单，但是它也有一个缺点，即在单链表中只能通过一个结点的引用访问其后续结点，而无法直接访问其前驱结点，
双向链表是通过上述定义的结点使用 pre 以及 next 域依次串联在一起而形成的。一个双向链表的结构如图所示。
6-3.循环链表
单向链表的循环
双向链表的循环
7.进入一步深造
下一步如何再深造呢?
去看java的
ArrayList和LinkedList,有了前面的基础，相信源码阅读就so easy 了。
8.推荐
能读到文章最后，首先得谢谢您对本文的肯定，你的肯定是对博主最大的鼓励。
你觉本文有帮助，那就点个👍
你有疑问，那就留下您的💬 怕把我弄丢了，那就把我⭐ 电脑不方便看，那就把发到你📲转载地址：http://gzhws.baihongyu.com/
你可能感兴趣的文章
通向财务自由之路01_导读
查看>>
通向财务自由之路02_成功的决定因素：你
查看>>
中低频量化交易策略研发01_引言
查看>>
中低频量化交易策略研发06_推进的择时策略
查看>>
史丹·温斯坦称傲牛熊市的秘密
查看>>
期货市场技术分析01_理论基础
查看>>
期货市场技术分析02_趋势的基本概念
查看>>
期货市场技术分析03_主要反转形态
查看>>
期货市场技术分析04_持续形态
查看>>
期货市场技术分析05_交易量和持仓兴趣
查看>>
TB交易开拓者入门教程
查看>>
TB创建公式应用dll失败 请检查用户权限，终极解决方案
查看>>
python绘制k线图(蜡烛图)报错 No module named 'matplotlib.finance
查看>>
talib均线大全
查看>>
期货市场技术分析06_长期图表和商品指数
查看>>
期货市场技术分析07_摆动指数和相反意见理论
查看>>
满屏的指标？删了吧，手把手教你裸 K 交易！
查看>>
不吹不黑 | 聊聊为什么要用99%精度的数据回测
查看>>
X 分钟速成 Python
查看>>
对于模拟交易所引发的思考
查看>>