线性表概述及单链表的Java实现
线性表概述及单链表的Java实现
一、线性表概述
线性表是指一组数据元素之间具有线性关系的元素序列,它表现为:除第一个元素没有直接前驱元素、最后一个元素没有直接后继元素外,其余所有元素都有且仅有一个直接前驱元素和直接后继元素。
根据存储结构的不同,线性表可以分为顺序存储和链式存储。
1、顺序存储
顺序存储结构是指用一段地址连续的存储单元依次存储线性表的数据元素。
数组就是采用顺序存储结构来存储的,数组元素的保存和读取操作的时间复杂度都是O(1),而插入和删除操作的时间复杂度为O(n),其优缺点如下:
优点 缺点
快速存取,时间复杂度O(1) 插入、删除时,时间复杂度较高为,O(n)
无需为表示元素之间的逻辑关系而增加额外的存储空间 存储空间固定,不易扩展,容易造成空间的浪费
2、链式存储
链式存储是指数据元素在内存空间中的存储地址可以是不连续的,元素之间的逻辑关系通过其附带的指示信息来进行关联。
单链表、双向链表、循环链表等都是采用链式存储结构进行存储的。
对于单链表来说,单个结点分为数据域和指针域,指针域附带的指示信息是下一个结点的存储地址。
单链表元素的读取、插入和删除的时间复杂度都是O(n),在插入和删除的操作上,如果我们不知道所要操作结点的指针,那么相比顺序存储结构的数组没有优势,在知道要操作结点的指针的情况下,对于插入或删除越频繁,单链表的效率优势就越明显。
比如插入10个元素,对于数组来说,每插入一个元素都要移动n-1个结点,每次的时间复杂度都是O(n),而对于单链表来说,只需要在第一次插入时找到目标位置结点的指针,后续插入都只需要通过移动指针来完成,时间复杂度为O(1)。
二、单链表的Java实现
1、定义单链表的存储结构
public class Node {
E element; Node next; Node() { } Node(E e) { this.element = e; this.next = null; }
}
一个Node结点包含两个属性,E element为存储的数据,指定为泛型;Node next为逻辑上的下一个结点的存储地址。
2、定义操作接口
public interface Collection {
void add(E e); void insert( E e, int index); void delete(int index); E get(int index); void modify( E e,int index); boolean isEmpty(); int size();
}
为集合、列表类操作定义一个包含公有行为的接口。
3、实现单链表
单链表的插入和删除操作可以抽象成两个步骤:
(1)找到目标结点
通过头节点进行遍历,直到找到目标结点;
(2)插入或删除;
插入:
//front为index - 1结点,即要插入位置的前一个结点
node.next = front.next;
front.next = node;
删除:
//front为index - 1结点,即要删除位置的前一个结点
node = front.next;
front.next = node.next;
//释放node结点
node = null;
单链表完整实现如下:
public class LinkedList implements Collection {
/** * 头指针 */ private Node<E> head; /** * 尾指针 */ private Node<E> tail; private int size; public LinkedList() { //初始化时创建空的头指针和尾指针,并指向同一个节点,后续增加元素时,尾指针后移,但头指针一直不变 head = new Node<E>(); tail = head; size = 0; } @Override public void add(E e) { Node node = new Node<E>(e); //设置尾指针的下一个节点为node tail.next = node; //设置node为新的尾指针 tail = node; //长度+1 size++; } @Override public void insert(E e, int index) { verifyIndex(index, size); Node node = new Node<E>(e); //先遍历找到index-1结点,然后在index-1结点插入,复杂度O(n) int i = 0; //index - 1结点 Node front = head; while (i < index) { front = front.next; i++; } node.next = front.next; front.next = node; size++; System.out.println(this.toString()); } @Override public void delete(int index) { verifyIndex(index, size - 1); //找到index-1节点 int i = 0; Node front = head; while (i < index) { front = front.next; i++; } Node target = front.next; front.next = target.next; target = null; size--; System.out.println(this.toString()); } @Override public E get(int index) { verifyIndex(index, size - 1); Node node = head; int i = 0; while (i <= index) { node = node.next; i++; } return (E) node.element; } @Override public void modify(E e, int index) { verifyIndex(index, size - 1); Node node = head; int i = 0; while (i <= index) { node = node.next; i++; } node.element = e; System.out.println(this.toString()); } @Override public boolean isEmpty() { return size <= 0; } @Override public int size() { return 0; } /** * 判断操作的索引是否合法, * @param index * @param end 右边界,插入时允许在末尾插入,即end = size * @return */ private void verifyIndex(int index, int end) { if (index < 0 || index > end) { throw new IndexOutOfBoundsException("invalid index for LinkedList:" + this.toString()); } } @Override public String toString() { Node node = head; StringBuilder stringBuilder = new StringBuilder(); while (node.next != null) { node = node.next; stringBuilder.append(node.element + " "); } return stringBuilder.toString(); }
}
Github下载地址
原文地址https://www.cnblogs.com/sqchen/p/10778472.html
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
JavaScript - ES6
ES6, 全称 ECMAScript 6.0 ,是 JavaScript 的下一个版本标准,2015.06 发版。 ES6 主要是为了解决 ES5 的先天不足,比如 JavaScript 里并没有类的概念,但是目前浏览器的 JavaScript 是 ES5 版本,大多数高版本的浏览器也支持 ES6,不过只实现了 ES6 的部分特性和功能。 ECMAScript 的背景 JavaScript 是大家所了解的语言名称,但是这个语言名称是商标( Oracle 公司注册的商标)。因此,JavaScript 的正式名称是 ECMAScript 。1996年11月,JavaScript 的创造者网景公司将 JS 提交给国际化标准组织 ECMA(European computer manufactures association,欧洲计算机制造联合会),希望这种语言能够成为国际标准,随后 ECMA 发布了规定浏览器脚本语言的标准,即 ECMAScript。这也有利于这门语言的开放和中立。 ECMAScript 的历史 ES6 是 ECMAScript 标准十余年来变动最大的一个版本,为其添加了许多新...
- 下一篇
Jpom一款简而轻的低侵入式Java运维、监控软件
Jpom(Java Project Online Management)Java项目在线管理 你为什么需要Jpom SpringBoot、Jboot等框架开发的项目通常是以Jar的方式在后台运行的,如果只有一两个项目,管理起来不是太麻烦,但是当项目多了以后,管理起来就不是那么方便了,当项目出现问题时,能够通过Jpom即时排查问题,问题解决后还可以直接上传修改后的Jar,项目的堆栈信息,服务器CPU、内存使用情况一目了然,不必再登录服务器管理。 当多个项目运行在同一台服务器时,运维人员通常也不只一个,如果每个人都登录服务器管理项目,难免会造成一些不必要的麻烦,甚至给服务器的安全性带来问题(服务器密码知道的人越多,越容易泄露),因为不需要登录服务器管理项目,维护人员不需要知道服务器的登录密码,只需要有Jpom的账号就行,Jpom本身可以通过权限管理,给不同用户不同的权限,这样也使得项目的稳定性得到提升。 Jpom可以在Linux和Windows服务器上运行,并且Jpom采用多节点模式,随时开启关闭节点服务器,节点分发减少运维人员上传、修改操作 Jpom 目标 一款简而轻的低侵入式Java运...
相关文章
文章评论
共有0条评论来说两句吧...