[当你的能力还驾驭不了你的目标时，就应该沉下心来，历练。]
图片.png
线性表(Linear List)
线性表是由零个或多个具有相同特性的数据元素组成的有限序列，是最基本且常用的一种线性结构(链表，数组，栈，队列都是线性结构），同时也是其他数据结构的基础。
注意
1.对于同一个线性表，其每一个数据元素的值虽然不同，但必须具有相同的数据类型；
2.数据元素之间具有一种线性的或“一对一”的逻辑关系;
3.线性表中的第一个元素无前驱(称为起始节点)，最后一个元素无后继(称为终端节点)，其他元素有且只有一个前驱和后继;
4.线性表的长度指其包含的元素个数，线性表的长度是有限的。
线性表的抽象数据类型(ADT)
线性表抽象数据类型主要包括两个方面：既数据集合和定义在该数据集合上的基本操作
基本操作
- 获取线性表的长度 len()：返回线性表中的数据元素的个数；
- 判断线性表是否为空 isEmpty()：判断线性表是否为空，若为空，则返回true；否则，返回为false。
- 获取元素 get(int index):返回线性表中的第i个数据元素的值;
- 插入元素 insert(int index, Object obj): 在线性表的第i个数据元素之前插入一个obj元素；
- 移除元素 remove(int index): 删除并返回线性表中第i个数据元素;
- 查找指定元素的索引 indexOf(Object obj)：返回线性表中首次出现的指定的元素的索引，若线性表中不包含此数据元素，则返回-1；
- 判断线性表中是否包含指定元素 contains(Object obj) ：
线性表抽象数据类型的Java描述
package com.datastruct.learn.list;
/**
* 线性表接口
*/
public interface IMyList {
//获取表的长度
public int len();
//判断是否为空
public boolean isEmpty();
//插入
public void insert(int index, Object obj);
//移除
public Object remove(int index);
//替换
public Object replace(int index, Object newObj);
//获取
public Object get(int index);
//查找
public boolean contains(Object obj);
public int indexOf(Object obj);
}
线性表的顺序存储结构--顺序表
所谓顺序表就是顺序存储的线性表。顺序存储是用一组地址连续的存储单元依次存放线性表中各个元素的存储结构。
顺序表的特点
- 实现顺序存储结构需要三个属性： 存储空间得起始位置 \ 线性表的最大存储容量 \ 线性表的当前长度
- 地址计算方法： loc(ai) = loc(a1)+(i-1)*C(个字节) ---线性表存储数据的时间复杂度为O(1) -->又称随机存储结构
- 线性表操作：(时间复杂度)
(1) 存储和获取元素： --O(1)
(2) 插入元素操作： --O(n)
(3) 删除元素： --O(n)
优缺点： 适用于存取元素，查找容易， 不适用于大量地插入和删除操作(需要大量移动元素)
Java代码(实现了前面定义的线性表接口)
package com.datastruct.learn.list;
/**
* 设计实现一个顺序线性表
* @author zengsk
* @date 2019/1/16
**/
public class cmArrayList implements IMyList {
private final int defaultSize = 10; //默认最大长度
private int maxSize; //最大长度
private int size;
private Object[] arrayList;
/**
* 构造函数，初始化顺序表
*/
public cmArrayList(){
init(defaultSize);
}
public cmArrayList(int _size){
init(_size);
}
private void init(int _size) {
maxSize = _size;
this.size = 0;
arrayList = new Object[maxSize];
}
/**
* 返回顺序表的长度
* @return
*/
@Override
public int len() {
return this.size;
}
/**
* 判断顺序表是否为空
* @return
*/
@Override
public boolean isEmpty() {
return this.size == 0;
}
/**
* 在任意索引位置插入元素
* @param index
* @param obj
*/
@Override
public void insert(int index, Object obj) {
if (size == maxSize)
throw new RuntimeException("顺序表已满，无法插入!!");
if (index < 0 || index >= size)
throw new RuntimeException("索引参数越界!!"+index);
//移动元素
for(int i = size - 1; i >= index; i--){
arrayList[i + 1] = arrayList[i];
}
//插入
arrayList[index] = obj;
size++;
}
/**
* 移除指定位置的元素，并返回该元素
* @param index
* @return
*/
@Override
public Object remove(int index) {
if (index > size - 1) {
throw new RuntimeException("索引错误" + index);
} else if (index < 0) {
throw new RuntimeException("索引错误" + index);
}
if(isEmpty())
throw new RuntimeException("顺序表为空，无法移除元素");
Object value = arrayList[index];
for(int i = index; i < this.size - 1; i++){
arrayList[i] = arrayList[i+1];
}
size--;
return value;
}
/**
* 替换元素
* @param index
* @param newObj
* @return
*/
@Override
public Object replace(int index, Object newObj) {
if(index < -1 || index >= size){
throw new RuntimeException("参数错误!!");
}
if(index == -1)
index = this.size - 1;
Object element = arrayList[index];
arrayList[index] = newObj;
return element;
}
/**
* 获取元素
* @param index
* @return
*/
@Override
public Object get(int index) {
if (index == -1)
return arrayList[this.size-1];
if(index < -1 || index > size - 1)
throw new RuntimeException("索引错误"+index);
return arrayList[index];
}
@Override
public boolean contains(Object obj) {
if(obj == null)
return false;
for(int i = 0; i < size-1; i++){
if(obj.equals(this.get(i)))
return true;
}
return false;
}
/**
* 元素索引查找
* @param obj
* @return
*/
@Override
public int indexOf(Object obj) {
if(obj == null)
return -1;
for(int i = 0; i < this.len(); i++){
if(obj.equals(this.get(i)))
return i;
}
return -1;
}
/**
* 在顺序表的尾部添加元素
* @param value
*/
public void add(Object value){
if(size == maxSize)
throw new RuntimeException("顺序表已满!!");
this.arrayList[size++] = value;
}
public void show(){
for (int i = 0; i < this.size; i++) {
System.out.print(arrayList[i]+"--");
}
}
}
顺序表必须占用一整块事先分配大小固定的存储空间，这样不便于存储空间的管理。为此提出了可以实现存储空间动态管理的链式存储方式——链表。
线性表的链式存储结构--单链表
单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：数据元素+ 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。
单链表结构
单链表的Java实现
- 首先自定义一个节点类来存放数据元素和指针
package com.datastruct.learn.list;
/**
* 结点类
* @author zengsk
* @date 2019/1/18
**/
public class Node {
public Object data;
public Node next = null;
public Node(){
this.data = null;
}
public Node(Object data){
this.data = data;
}
/**
* 显示此结点
*/
public void display(){
System.out.println(this.data.toString());
}
}
- 基于上面的节点类实现单链表结构的常见操作(增删改查)
package com.datastruct.learn.list;
/**
* 设计实现一个单链表结构---method 01
* @author zengsk
* @date 2019/1/17
**/
public class cmLinkList {
private Node head;
private int size;
public cmLinkList(){
this.head = new Node();
this.size = 0;
}
/**
* 获取链表长度
* @return
*/
public int len(){
return this.size;
}
/**
* 判断链表是否为空
* @return
*/
public boolean isEmpty(){
return this.size == 0;
}
/**
* 头插法
* @param value
*/
public void addFirst(Object value){
Node cur = new Node(value);
cur.next = head.next;
head.next = cur;
size++;
}
/**
* 尾插法
* @param value
*/
public void addTail(Object value){
Node pos = head;
while(pos.next != null){
pos = pos.next;
}
Node cur = new Node(value);
pos.next = cur;
cur.next = null;
size++;
}
/**
* 将数据插入到指定的位置
* @param index
* @param value
* @return
*/
public boolean insert(int index, Object value){
if(index < 0 || index > this.size){
return false;
}
//定位到插入点
int i = 0;
Node pos = head;
while(pos.next != null && i < index){
pos = pos.next;
i++;
}
//插入操作
Node cur = new Node(value);
cur.next = pos.next;
pos.next = cur;
size++;
return true;
}
/**
* 打印单链表的数据
*/
public void show(){
Node pos = head;
while(pos.next != null){
System.out.print(pos.next.data+"-->");
pos = pos.next;
}
}
/**
* 移除指定索引位置的元素
* @param index
* @return
*/
public Object remove(int index){
Object val = null;
if(isEmpty()){
throw new RuntimeException("链表为空，无法移除!!");
}
if(index < 0 || index > size-1)
throw new RuntimeException("索引错误"+index);
//定位
Node pos = head;
for(int i = 0; i < index; i++){
pos = pos.next;
}
val = pos.next.data;
pos.next = pos.next.next;
size--;
return val;
}
/**
* 获取元素
* @param index
* @return
*/
public Object get(int index){
if(isEmpty()){
throw new RuntimeException("链表为空");
}
if(index < 0 || index > size-1) {
throw new RuntimeException("索引错误");
}
//定位
Node pos = head;
for(int i = 0; i < index; i++){
pos = pos.next;
}
return pos.next.data;
}
/**
* 判断是否包含
* @param value
* @return
*/
public boolean contains(Object value){
Node pos = head;
while(pos.next != null){
pos = pos.next;
if(pos.data.equals(value)) {
return true;
}
}
return false;
}
/**
* 获取元素索引
* @param value
* @return
*/
public int indexOf(Object value){
int i = 0;
Node pos = head;
while(pos.next != null){
pos = pos.next;
if(pos.data.equals(value)) {
return i;
}
i++;
}
return -1;
}
}
- 此外，还可以利用Java的内部类来实现单链表结构
package com.datastruct.learn.list;
/**
* 利用java的内部类来实现链表结构
* @author zengsk
* @date 2019/1/17
**/
public class cmLinkList02 {
//结点内部类
class InNode{
private Object data;
private InNode next = null;
public InNode(){
this.data = null;
}
public InNode(Object data) {
this.data = data;
}
}
private InNode head;
private int size;
public cmLinkList02(){
head = new InNode();
size = 0;
}
public int len(){
return this.size;
}
public boolean isEmpty(){
return this.size == 0;
}
public void show(){
InNode pos = head;
while(pos.next != null){
System.out.print(pos.next.data+"-->");
pos = pos.next;
}
}
/**
* 头插法
* @param value
*/
public void addFirst(Object value){
InNode _node = new InNode(value);
_node.next = head.next;
head.next = _node;
size++;
}
/**
* 尾插法
* @param value
*/
public void addTail(Object value){
InNode pos = head;
while(pos.next != null){
pos = pos.next;
}
InNode _node = new InNode(value);
pos.next = _node;
_node.next = null;
size++;
}
/**
* 移除元素
* @param index
* @return
*/
public Object remove(int index){
Object val = null;
if(index < 0 || index > size-1)
throw new RuntimeException("索引错误"+index);
//定位
int i = 0;
InNode pos = head;
while(pos.next != null && i < index){
pos = pos.next;
i++;
}
val = pos.next.data;
pos.next = pos.next.next;
size--;
return val;
}
/**
* 判断元素是否包含
* @param value
* @return
*/
public boolean contains(Object value){
InNode pos = head;
while(pos.next != null){
pos = pos.next;
if(pos.data.equals(value)) {
return true;
}
}
return false;
}
/**
* 获取指定位置的元素
* @param index
* @return
*/
public Object get(int index){
if(isEmpty()){
throw new RuntimeException("链表为空");
}
if(index < 0 || index > size-1) {
throw new RuntimeException("索引错误");
}
//定位
InNode pos = head;
for(int i = 0; i < index; i++){
pos = pos.next;
}
return pos.next.data;
}
/**
* 获取指定元素的索引
* @param value
* @return
*/
public int indexOf(Object value){
int i = 0;
InNode pos = head;
while(pos.next != null){
pos = pos.next;
if(pos.data.equals(value)) {
return i;
}
i++;
}
return -1;
}
}
总结
顺序表 VS 单链表
顺序表
优点：
（1）数据是连续存放，地址连续；
（2）存取速度高效，通过下标来直接访问；
缺点：
（1）插入和删除比较慢，每一次增加或者删除，后面的所有数据元素需要向前移动一位或者向后移动一位；
（2）预分配内存，可能导致空间浪费；
时间复杂度 :查找操作为O(1) ,插入和删除操作为O(n)。
链表
优点：
（1）插入和删除速度快，保留原有的物理顺序，在插入或者删除一个元素的时候，只需要改变指针指向即可；
（2）可以动态增长长度；
（3）动态分配内存空间，不用事先开辟内存；
缺点：
（1）占用额外的空间以存储指针，存储地址不连续；
（2）查找速度比较慢，因为在查找时，需要循环链表。
时间复杂度 :查找操作为O(n) ,插入和删除操作为O(1)。
网友评论