您好,登录后才能下订单哦!
本篇内容介绍了“什么是线性表、顺序表、链表”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!
首先来看一下线性表,顺序表,和链表之间的区别和联系:
线性表:
逻辑结构, 就是对外暴露数据之间的关系,不关心底层如何实现,数据结构的逻辑结构大分类就是线性结构和非线性结构,而顺序表、链表都是一种线性表。
线性表结构存储的数据往往是可以依次排列的,就像小朋友手拉手,每位学生的前面和后面都仅有一个小朋友和他拉手,具备这种“一对一”关系的数据就可以使用线性表来存储。
顺序表、链表:物理结构,他是实现一个结构实际物理地址上的结构。比如顺序表就是用数组实现。而链表用指针完成主要工作。不同的结构在不同的场景有不同的区别。
我们首先定义一个线性表的抽象类,主要包括增加、查找、删除等方法。后面分别用顺序表和链表做实现:
/** * 线性表 * * @author ervin * @Date 2021/4/18 */ public interface ListInterface<T> { /** * 初始化 * @param size */ void init(int size); /** * 长度 * @return */ int length(); /** * 是否为空 * @return */ boolean isEmpty(); /** * 获取元素下标 * @param t * @return */ int eleIndex(T t); /** * 根据index获取数据 * @param index * @return * @throws Exception */ T getEle(int index) throws Exception; /** * 根据index插入数据 * @param index * @param t * @throws Exception */ void add(int index,T t) throws Exception; /** * 删除元素 * @param index * @throws Exception */ void delete(int index) throws Exception; /** * 尾部插入元素 * @param t * @throws Exception */ void add(T t) throws Exception; /** * 修改 * @param index * @param t * @throws Exception */ void set(int index,T t) throws Exception; }
顺序表是基于数组实现的,由于数组中的数据时存储的一块连续的内存中,插入、删除元素会导致部分元素的移动,效率较低,但是查询效率却十分快。
顺序表元素插入示意图:
这里以插入为例做说明,删除操作正好相反。
如果要删除下标为 2 的元素时,下标为 2 及之后的元素,从左至右,依次左移一位。
另外,顺序表的插入需要考虑 “扩容”
代码实现:
/** * 顺序表实现 * * @author ervin * @Date 2021/4/18 */ public class SeqList<T> implements ListInterface<T> { //数组存放数据 private Object[] date; private int length; public SeqList() { //初始大小默认为10 init(10); } @Override public void init(int initSize) { this.date = new Object[initSize]; length = 0; } @Override public int length() { return this.length; } @Override public boolean isEmpty() { //是否为空 return this.length == 0; } @Override public int eleIndex(T t) { for (int i = 0; i < date.length; i++) { if (date[i].equals(t)) { return i; } } return -1; } @Override public T getEle(int index) throws Exception { if (index < 0 || index > length - 1) { throw new Exception("数值越界"); } return (T) date[index]; } @Override public void add(T t) throws Exception { //尾部插入 add(length, t); } @Override public void add(int index, T t) throws Exception { if (index < 0 || index > length) { throw new Exception("数值越界"); } //扩容 if (length == date.length) { Object[] newDate = new Object[length * 2]; for (int i = 0; i < length; i++) { newDate[i] = date[i]; } date = newDate; } //后面元素后移动 for (int i = length - 1; i >= index; i--) { date[i + 1] = date[i]; } //插入元素 date[index] = t; length++; } @Override public void delete(int index) throws Exception { if (index < 0 || index > length - 1) { throw new Exception("数值越界"); } //index之后元素前移动 for (int i = index; i < length; i++) { date[i] = date[i + 1]; } length--; } @Override public void set(int index, T t) throws Exception { if (index < 0 || index > length - 1) { throw new Exception("数值越界"); } date[index] = t; } }
链表存储数据的空间是不连续的,有一个个 “node” 连接起来,形成链表,每一个 “node” 不仅存放数据本身,还存放了下一个 “node” 的地址。
如图:
链表查找元素,需要遍历查找,效率较低;插入删除元素,只需要,修改指针,效率很高。
链表无需考虑 “扩容”
链表元素插入示意:
链表元素删除示意图:
代码实现:
/** * 链表实现 * * @author ervin * @Date 2021/4/18 */ public class LinkList<T> implements ListInterface<T> { private static class Node<T> { T item; Node<T> next; Node(T element, Node<T> next) { this.item = element; this.next = next; } } Node header; private int size; public LinkList(){ this.header = new Node(null,null); this.size = 0; } @Override public void init(int size) { } @Override public int length() { return this.size; } @Override public boolean isEmpty() { return this.length() == 0; } @Override public int eleIndex(T t) { Node n = header.next; int index = 0; while (n.next != null){ if (n.item.equals(t)){ return index; } index++; n = n.next; } //找不到返回-1 return -1; } @Override public T getEle(int index) throws Exception { Node n = getNode(index); return (T)n.item; } @Override public void add(int index, T t) throws Exception { //考虑第一个元素 if (index == 0){ this.header.next = new Node(t,null); } else { Node n = getNode(index - 1); //获取到index的上一个元素n, n指向新建的元素,同时新建的元素指向n的下一个元素 n.next = new Node(t,n.next); } this.size++; } @Override public void delete(int index) throws Exception { //index为0时,不用去获取上一个元素, if (index == 0){ this.header.next = getNode(1); } else { Node n = getNode(index - 1); n.next = n.next.next; } size--; } @Override public void add(T t) throws Exception { add(size,t); } @Override public void set(int index, T t) throws Exception { Node node = getNode(index); node.item = t; } private Node getNode(int index) throws Exception { if (index<0 || index > this.size-1){ throw new Exception("数组越界"); } Node n = header.next; for (int i = 0;i<index;i++){ n = n.next; } return n; } }
在实际应用中双链表的应用多一些,就比如LinkedList
双链表的一个节点,有存储数据的data,也有后驱节点next(指针),指向下一个节点,这和单链表是一样的,但它还有一个前驱节点pre(指针),指向上一个节点。
这样的设计,牺牲了额外的内存类存储 “pre” 指针,但是相比单链表只能 “从头向尾” 查找,双链表不仅可以 “从头向尾”,“从尾向头”,甚至可以从中间开始查找,在有些时候,双链表的查找效率要比单链表快很多。
这一点,在 JDK LinkedList
的源码中有体现,我们来看它的 get(int index)
方法,
接着点进去,看它的 node(int index)
方法
如果 index
位于链表的前半部分,则从前开始查找;反之,则从后开始查找。
单链表查询速度较慢,因为他需要从头遍历,插入删除速度较快;内存利用率高,不会浪费内存,大小没有固定,拓展很灵活
顺序表查询速度较快,插入删除速度较慢
Java中的Arraylist和LinkedList就是两种方式的代表,不过LinkedList使用双向链表优化
双链表的查询速度要优于单链表
从存储结构来看,每个双链表的节点要比单链表的节点多一个指针,而长度为n就需要 n*length(这个指针的length在32位系统中是4字节,在64位系统中是8个字节) 的空间,这在一些追求时间效率不高应用下并不适应,因为它占用空间大于单链表所占用的空间;这时设计者就会采用以时间换空间的做法,这是一种工程总体上的衡量。
“什么是线性表、顺序表、链表”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识可以关注亿速云网站,小编将为大家输出更多高质量的实用文章!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。