Java数据结构之线性表

线性表是其组成元素间具有线性关系的一种数据结构,对线性表的基本操作主要有,获取元素,设置元素值,遍历,插入,删除,查找,替换,排序等。而线性表可以采用顺序储存结构和链式储存结构,本节主要讲解顺序表、单链表以及双链表的各种基本操作。

1:线性表抽象的数据类型

线性表:是由n(n>=0)个数据相同的元素组成的有限序列。线性表的定义接口如下

public interface IList<T> {
 /**
 * 是否为空
 * @return
 */
 boolean isEmpty();
 /**
 * 表的长度
 * @return
 */
 int length();
 /**
 * 根据索引获取长度
 * @param i
 * @return
 */
 T get(int i);
 /**
 * 设置第i个元素值为x
 * @param i
 * @param x
 */
 void set(int i,T x);
 /**
 * 在线性表最后插入x元素
 * @param x
 */
 void append(T x);
 /**
 * 异常第i个元素并返回值
 * @param i
 * @return
 */
 T remove(int i);
 /**
 * 删除线性表中所有元素
 */
 void removeAll();
 /**
 * 查询首次出现关键字为key的元素
 * @param key
 * @return
 */
 T search(T key);
 void insert(int i,T x);
 /**
 * 升序添加
 * @param x
 */
 void insert(T x);
 /**
 * 升序删除
 * @param x
 */
 void remove(T x);
}

2:线性表顺序表示和实现

线性表的顺序存储结构是一组连续的内存单元依次存放的线性表的数据元素,元素的物理地址和逻辑地址次序是相同的。我们叫做这种存储方式为顺序表。

由于数组只能进行赋值和取值,而且长度是不可变化的,所以给我们的操作带来很大的麻烦,但是用顺序表就可以进行删除,插入等操作。其实顺序表内部同样适用数组来表示的,只不过这个数据我们可以改变他的长度,这样说来我们就好办了,首先我们要为顺序表定义一个数组,同时在定义一个值来记录线性表的长度,所以第一步我们就有了如下

准备事件做好了以后,我们肯定会对顺序表进行初始化,刚刚开始数组的长度肯定是0。但是我们必须要为数组开辟一个内存空间,来存储要插入的元素,如下

其他的都比较简单,我主要说下插入和删除

插入一个元素的时候,如果插在第i个位置,那么意味着它后面所有的元素前部往后面移一位,但是我们必须把i个位置留出来给即将插入的元素。但是我们还必须考虑,如果这个数组满了的情况。如果满了,我们必须重新为顺序表开辟内存空间,然后把以前的元素进行迁移到新的表中,java实现如下

代码看出,我们把从第i个位置的元素全部往后移(包括第i个元素)然后在把第i个元素进行赋值

删除第i个元素,这个和上面的正好相反,如果删除第i个元素意味着在i之后的元素前部往前移一位。

3:顺序表操作效率分析

因为顺序表是具有索引的,所以get()和set()效率极高,时间复杂度都是O(n)。

从上面发现,在插入和删除的时候都是需要大量元素的移动,因为在各个位置插入元素的概率相同,所以平均插入一个元素要移动的元素是2/n。那么它的时间复杂度就是O(n),如果要容器满了,那么就需要申请更大的容器来存储新加入的元素,那么效率会更加的低下。所以顺序表的静态性好,动态性就很差了,所以在选择的时候就要注意一下。

4:单链表的实现

线性表的链式存储结构是用若干地址分散的存储单元存储数据元素,逻辑上相邻的2个元素,物理地址不一定相同,这么说来就充分的利用了内存中的地址。但是我们必须用附加信息来连接2个不同的数据元素,所以这里就引进了2个概念,数据域(data)和地址域(next),其中数据域存储的是这个元素的值,地址域存储下一个元素的地址。其中数据域和地址域联合起来我们称为节点(node)。如果只有后继节点没有前驱节点我们就称为单链表,那么现在我们来看看单链表的实现。

首先我们要定义一个节点Node

public class Node<T> {
 public T data;//数据域
 public Node next;//地址域
 public Node() {
 this(null, null);
 }
 public Node(T data, Node next) {
 this.data = data;
 this.next = next;
 }
}

现在我们想象一下,A(x)和B(y)2个节点,其中A的后继节点是B,那么我们怎么表示呢,如下

Node<String> A=new Node<T>(x,null);
Node<String> B=new Node<T>(y,null);
A.next=B。

也可以把A写成Node<String> A=new Node<T>(x,B);

ok现在我们正式开始实现一个带有头节点的单链表

我们可以把头指针想象成一个指针来便于我们的操作,我们先看如何实现单链表的长度

public int length() {
 int i = 0;
 Node<T> p = this.head.next;
 while (p != null) {
  p = p.next;
  i++;
 }
 return i;
 }

因为这是一个链式的结构,我们无法得知长度,只能通过循环来知道链表中节点的个数,因为头指针的后继节点就是我们链表中第一个节点,所以我们就可以这样往下循环来得知。

获取第i个节点的值

同样我们无法直接获取节点,这个时候同样采用循环,如果循环第i个元素值等于我们i那么我们就获取这个节点,然后得到值

public T get(int i) {
 if (i >= 0) {
  Node<T> p = this.head;
  for (int j = 0; j <= i; j++) {
  p = p.next;
  }
  if (p!=null){
  return p.data;
  }
 }
 return null;
 }

在第i个位置插入一个节点

首先我们必须要找到要插入节点的前驱节点,然后前驱节点的后继节点指向这个新节点,新节点的后继节点指向原来前驱节点的后继节点。

从代码看出我们是根据头节点进行循环的。加入p.next!=null的目的是为了当循环到最后一个节点的时候就停止,不在继续了。

移除第i个节点

如果我们要删除第i个节点和上面差不多,同样我们要找到这个第i个节点的前驱节点,和上面代码差不多。

在链表后追加一个节点。

如果传统的话我们可以采取insert(this.length,x);但是这样一来计算长度的时候就需要遍历链表无疑速度减慢,只需要如下

insert(Integer.MAX_VALUE, x)即可,从插入代码可以看到当循环到最后一个节点就不会继续了,然后把新的节点加入最后即可。

5:排序单链表

排序首先我们需要我们的元素要继承comparable。

我们就说插入和删除。先说插入

如果插入一个元素,我们先获取要插入这个节点的前驱节点和后继节点。(x.compareTo(y)<0 表示小于y)

其中p.data.next.compareTo(x)<0如果跳出循环说明p节点值大于或等于x

如果删除一个元素,和上面的基本一样,但是要加上一个判断如下

其中通过上面判断我们知道p节点大于或等于x节点了,所以需要再次判断。

6:单链表操作效率分析

单链表在获取元素和设置元素的时候都需要进行遍历所以时间复杂度O(n)

如果在p节点插入或删除元素,只需要修改链的后继节点的地址即可所以时间复杂度O(1),但是如果插入类似insert(i,x)就需要进行遍历了,那么时间复杂度就是O(n).

对单链表进行插入和删除只需要改变少量节点的链,不需要移动元素,单链表的插入和删除都是动态申请和释放的,不需要预先分配存储空间,从而不会因为存储空间不足而进行扩容,提高了运行效率。

7:双链表的实现

双链表和单链表大多是相同的只不过多了前驱节点,现在我们先定义一下双链表

我们这里来演示循环双链表的实现。基本和单链表相同只不过如果为空链表那么它的后继节点就是头节点。ok我们先来看

求双链表的长度(基本和单链表一样后面一样的不在写了)因为是循环双链表最后一个节点的后继节点为

我们这里只说插入和删除(其他基本一样和单链表)

插入

同样我们需要找到要插入的节点

其中p.next!=this.head表示如果是最后一个节点则跳出循环。其中要插入的节点在p节点之后,然后我们就好理解了。

删除

和上面的差不多

8:循环双链表

根本和单链表一样。也是先找到节点的位置然后插入或删除

总结:主要是回顾一下线性表,通过对线性表的了解,在以后我们看java容器源码的时候会带来极大的帮助

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,同时也希望多多支持我们!

(0)

相关推荐

  • java线性表的存储结构及其代码实现

    Java数据结构学习笔记第一篇: 用程序后在那个的数据大致有四种基本的逻辑结构: 集合:数据元素之间只有"同属于一个集合"的关系 线性结构:数据元素之间存在一个对一个的关系 树形结构:数据元素之间存在一个对多个关系 图形结构或网状结构:数据元素之间存在多个对多个的关系 对于数据不同的逻辑结构,计算机在物理磁盘上通常有两种屋里存储结构 顺序存储结构 链式存储结构 本篇博文主要讲的是线性结构,而线性结构主要是线性表,非线性结构主要是树和图. 线性表的基本特征: 总存在唯一的第一个数据元素

  • Java数据结构(线性表)详解

    线性表的链式存储与实现 实现线性表的另一种方法是链式存储,即用指针将存储线性表中数据元素的那些单元依次串联在一起.这种方法避免了在数组中用连续的单元存储元素的缺点,因而在执行插入或 删除运算时,不再需要移动元素来腾出空间或填补空缺.然而我们为此付出的代价是,需要在每个单元中设置指针来表示表中元素之间的逻辑关系,因而增加了额外的存储空间的开销. 单链表 链表是一系列的存储数据元素的单元通过指针串接起来形成的,因此每个单元至少有两个域,一个域用于数据元素的存储,另一个域是指向其他单元的指针.这里具有

  • java 线性表接口的实例详解

    java 线性表接口的实例详解 前言: 线性表是其组成元素间具有线性关系的一种线性结构,对线性表的基本操作主要有插入.删除.查找.替换等,这些操作可以在线性表的任何位置进行.线性表可以采用顺序存储结构和链式存储结构表示. 本接口的类属于dataStructure包的linearList子包.线性表接口LList声明如下,描述线性表的取值.置值.插入.删除等基本操作. package dataStructure.linearList; public interface LList<E> { bo

  • java线性表排序示例分享

    大家可以先看一下这个静态方法public static <T> void sort(List<T> list, Comparator<? super T> c) 1.先定义一个模型: 复制代码 代码如下: package model; /** * User.java *  * @author 梁WP 2014年3月3日 */public class User{    private String userName;    private int userAge; pub

  • Java数据结构之线性表

    线性表是其组成元素间具有线性关系的一种数据结构,对线性表的基本操作主要有,获取元素,设置元素值,遍历,插入,删除,查找,替换,排序等.而线性表可以采用顺序储存结构和链式储存结构,本节主要讲解顺序表.单链表以及双链表的各种基本操作. 1:线性表抽象的数据类型 线性表:是由n(n>=0)个数据相同的元素组成的有限序列.线性表的定义接口如下 public interface IList<T> { /** * 是否为空 * @return */ boolean isEmpty(); /** *

  • java数据结构基础:线性表

    目录 前言 需求分析 编码 add方法 getIndex方法 pop方法 insert方法 getAll 全部代码 总结 前言 其实线性表在生活中和栈的结构差不多.昨天总结了一篇单链表,也是线性表的一种. 今天用另一种写法来控制指针的移动实现数据的顺序存储结构. 需求分析 首先要明确,这种顺序存储结构的线性表底层用什么.根据之前查看过的源码来看,list一般都是以数组为底层.我们也不例外. 其次,我们还得去定义好线性表的长度,以及每个元素的指针. private Object[] arr; //

  • Java数据结构之顺序表和链表精解

    目录 前言 1. 顺序表 代码实现 2. 链表 链表图解 代码实现 前言 两个数据结构:顺序表和链表 数据结构是一门学科,和语言无关. 数据 + 结构:一种描述和组织数据的方式. 1. 顺序表 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储.在数组上完成数据的增删查改.其逻辑上和物理上都是连续的. 问题引入:一个数组放在这,我们如何才能自己不去数,让程序自己进行计数? 答:在引入变量,每次放一个元素就更新一次.(如下图,为问题的示意) 也就是说顺序表的底层

  • Java数据结构之顺序表篇

    目录 一.线性表 二.顺序表 1.概念及结构 2.顺序表的实现 打印顺序表 获取顺序表的有效长度 在pos位置新增元素 判断是否包含某个元素 查找某个元素对应的位置 获取/查找pos位置的元素 给pos位置的元素设为value 删除第一次出现的关键字key 清空顺序表 3.顺序表的优.缺点 三.顺序表的实现代码汇总 一.线性表 线性表( linear list ) 是 n 个具有相同特性的数据元素的有限序列. 线性表是一种在实际中广泛使用的数据结构,常见 的线性表:顺序表.链表.栈.队列.字符串

  • Java数据结构之顺序表的实现

    目录 前言 一.顺序表 1.1 什么是顺序表 二.简单实现顺序表 2.1 创建顺序表 2.2 打印顺序表 2.3 获取顺序表长度 2.4 在 pos 位置新增元素 2.5 判定是否包含某个元素 2.6 查找某个元素对应的位置 2.7 获取 pos 位置的元素 2.8 给 pos 位置的元素设为 value 2.9 删除你想要删除的元素 2.10 清空顺序表 三.MyArrayList.java 四.Test.java 前言 线性表(linear list)是n个具有相同特性的数据元素的有限序列.

  • C语言数据结构之线性表的链式存储结构

    1.什么是线性表的链式存储结构 -链表 存储结点:包括元素本身的信息,还有元素之间的关系逻辑的信息 这个结点有:数据域和指针域 一个指针域:指向后继结点, 单链表 二个指针域: 指向前继结点,还有一个指向后继结点 双链表 2.原理是: s=(LinkNode *)malloc(sizeof(LinkNode));// s->data=e; //这里赋值了 s->next=p->next; // p->next=s; //这里把指针s给到了p 结点a-> 结点b -> 结

  • java数据结构实现顺序表示例

    复制代码 代码如下: import java.util.Arrays;/** * 顺序线性表的实现 */public class LineList<E>{ private int size;   //长度 private Object[] array;  //底层数组 private final int default_length=16; //默认长度 /**  * 无参构造方法  */ public LineList(){  size = 0;  //使用默认长度构造数组  array =

  • python数据结构之线性表的顺序存储结构

    用Python仿照C语言来实现线性表的顺序存储结构,供大家参考,具体内容如下 本文所采用的数据结构模板为 <数据结构教程>C语言版,李春葆.尹为民等著. 该篇所涉及到的是线性表的顺序存储结构. 代码: # !/usr/bin/env python # -*- coding: utf-8 -*- __author__ = 'MrHero' class Node(object): """ 线性表的存储结构 和 C 语言中的链式存储结构类似 ""&q

  • Java 精炼解读数据结构的顺序表如何操作

    目录 前言 一.什么是顺序表 顺序表的概念及结构 创建顺序表 获取顺序表长度 在pos位置新增元素 判定是否包含某个元素 查找某个元素对应的位置 获取pos位置的元素 给pos位置的元素设为value 删除你想要删除的元素 总结: 前言 线性表(linear list)是n个具有相同特性的数据元素的有限序列. 线性表是一种在实际中广泛使用的数据结构,常见 的线性表:顺序表.链表.栈.队列.字符串... 线性表在逻辑上是线性结构,也就说是连续的一条直线.但是在物理结构上并不一定是连续的,线性表在物

随机推荐

其他