数据结构(Java描述)之线性表

基础概念

数据结构:是相互之间存在一种或多种关系的数据元素的集合。

逻辑结构和物理结构

关于数据结构,我们可以从逻辑结构和物理结构这两个维度去描述

逻辑结构是数据对象中数据元素之间的关系,是从逻辑意义上去描述的数据之间的组织形式。

逻辑结构有4种:

  • 集合结构(数据元素之间仅以集合的方式体现,元素之间没有别的关系)
  • 线性结构(数据元素之间存在一对一的关系)
  • (数据元素之间为一对多或多对一的关系)
  • (数据元素之间为多对多的关系)

物理结构则是逻辑结构在计算机中内存中的存储形式,分为两种:

  • 顺序存储结构
  • 链式存储结构

线性表(list)

线性表是零个或多个数据元素的的有限序列

线性表是线性结构,元素之间存在一对一的关系,线性表可通过顺序和链式两种方式来实现。

顺序存储结构,是用一段地址连续的存储单元依次存储线性表的数据元素

  

链式存储结构,用一组任意的存储单元来存储数据元素,不要求物理存储单元的连续性,由一系列结点组成,每个结点除了要存储数据外,还需存储指向后继结点或前驱结点的存储地址。

顺序存储和链式存储对比

  • 顺序存储结构

    • 优点

      • 实现比较简单
      • 查找指定位置的元素效率很快,时间复杂度为常数阶O(1) 
      • 无需额外存储元素之间的逻辑关系(链式存储由于存储空间随机分配,需要存储元素之间的逻辑关系)
    • 缺点
      • 需要预先分配存储空间,如果数据元素数量变化较大,很难确定存储容量,并导致空间浪费
      • 若频繁进行插入删除操作,则可能需要频繁移动大量数据元素
  • 链式存储结构

    • 优点

      • 不需要提前分配存储空间,元素个数不受限制
      • 对于插入删除操作,在已找到目标位置前提下,效率很高,仅需处理元素之间的引用关系,时间复杂度为O(1)
    • 缺点
      • 实现相对复杂
      • 查找效率较低,最坏情况下需要遍历整张表
      • 由于物理存储位置不固定,需要额外存储数据元素之间的逻辑关系

链式存储代码实现

单链表

package listdemo;
/**
 * Created by chengxiao on 2016/10/18.
 */
public class MyLinkedList {
    /**
     * 指向头结点的引用
     */
    private Node first ;
    /**
     * 线性表大小
     */
    private int size;
    /**
     * 结点类
     */
    private static class Node{
        //数据域
        private int data;
        //指向后继结点的引用
        private Node next;
        Node(int data){
            this.data = data;
        }
    }
    /**
     * 从头部进行插入
     * 步骤:1.新结点的next链指向当前头结点;2.将first指向新节点
     * 时间复杂度:O(1)
     * @param data
     */
    public void insertFirst(int data){
        Node newNode = new Node(data);
        newNode.next = first;
        first = newNode;
        size++;
    }
    /**
     * 从头部进行删除操作
     * 步骤:1.将头结点的next链置空 2.将first引用指向第二个结点
     * 时间复杂度为:O(1)
     * @return
     */
    public boolean deleteFirst(){
        if(isEmpty()){
            return false;
        }
        Node secondNode = first.next;
        first.next = null;
        first = secondNode;
        size--;
        return true;
    }
    /**
     * 取出第i个结点
     * 步骤:从头结点进行遍历,取第i个结点
     * 时间复杂度:O(n),此操作对于利用数组实现的顺序存储结构,仅需常数阶O(1)即可完成。
     * @param index
     * @return
     */
    public int get(int index) throws Exception {
        if(!checkIndex(index)){
            throw new Exception("index不合法!");
        }
        Node curr = first;
        for(int i=0;i<index;i++){
            curr = curr.next;
        }
        return curr.data;
    }
    /**
     * 遍历线性表
     * 时间复杂度:O(n)
     */
    public void displayList(){
        Node currNode = first;
        while (currNode!=null){
            System.out.print(currNode.data+" ");
            currNode = currNode.next;
        }
        System.out.println();
    }

    /**
     * 链表是否为空
     * @return
     */
    public boolean isEmpty(){
        return first == null;
    }

    /**
     * index是否合法
     * @param index
     * @return
     */
    private boolean checkIndex(int index){
        return index >= 0 && index < size;
    }
    /**
     * 链表大小
     * @return
     */
    public int size() {
        return size;
    }
    public static  void main(String []args) throws Exception {

        MyLinkedList myLinkedList = new MyLinkedList();
        //从头部插入
        myLinkedList.insertFirst(1);
        myLinkedList.insertFirst(2);
        myLinkedList.insertFirst(3);
        myLinkedList.insertFirst(4);
        //遍历线性表中元素
        myLinkedList.displayList();
        //获取第二个元素
        System.out.println(myLinkedList.get(2));
        //删除结点
        myLinkedList.deleteFirst();
        myLinkedList.displayList();
    }
}

输出结果

  4 3 2 1
  2
  3 2 1 

双端链表 

  上面罗列了线性表中的几种基本操作,考虑下,如果要提供一个在链表尾部进行插入的操作insertLast,那么由于单链表只保留了指向头结点的应用first,需要从头结点不断通过其next链找后继结点来遍历,时间复杂度为O(n)。其实,我们可以在保留头结点引用的时候,也保留一个尾结点的引用。这样,在从尾部进行插入时就方便多了

  双端链表同时保存对头结点和对尾结点的引用

    /**
     * 指向头结点的引用
     */
    private Node first ;
    /**
     * 指向尾结点的引用
     */
    private Node rear;

从尾部进行插入

  /**
     * 双端链表,从尾部进行插入
     * 步骤:将当前尾结点的next链指向新节点即可
     * 时间复杂度:O(1)
     * @param data
     */
    public void insertLast(int data){
        Node newNode = new Node(data);
        if(isEmpty()){
            first = newNode;
            rear = newNode;
            size++;
            return;
        }
        rear.next = newNode;
        rear = newNode;
        size++;
    }

做其他操作的时候也需注意保持对尾结点的引用,此处不再赘述。

双向链表

 再考虑下,如果我们要提供一个删除尾结点的操作,步骤很简单:在删除尾结点的过程中需要将其前驱结点(即倒数第二个结点)的next链引用置为空,但由于我们的链表是单链表,一条道走到黑,要找倒数第二个结点得从头开始遍历,这种情况下,我们就可以考虑使用双向链表。

  双向链表的的每一个结点,包含两个指针域,一个指向它的前驱结点,一个指向它的后继结点。

          

  /**
     * 删除尾结点
     * 主要步骤:1.将rear指向倒数第二个结点 2.处理相关结点的引用链
     * 时间复杂度:O(1)
     * @return
     */
    public void deleteLast() throws Exception {
        if(isEmpty()){
            throw new Exception("链表为空");
        }
        Node secondLast = rear.prev;
        rear.prev = null;
        rear = secondLast;
        if(rear == null){
            first = null;
        }else{
            rear.next = null;
        }
        size--;
    }

其他操作同理,在过程中需要同时保持对结点的前驱结点和后继结点的引用,删除操作时,需要注意解除废弃结点的各种引用,便于GC。

总结

  本文对数据结构的一些基本概念,逻辑结构和物理结构,线性表等概念进行了基本的阐述。同时,介绍了线性表的顺序存储结构和链式存储结构,对线性表的链式存储结构(单链表,双端链表,双向链表),使用Java语言做了基本实现。数据结构的重要性毋庸置疑,它是软件设计的基石,由于自己非科班出身,虽曾自学过一段时间,也不够系统,最近希望能重新系统地梳理下,本篇就当自己数据结构再学习的开篇吧,共勉。

  

时间: 10-21

数据结构(Java描述)之线性表的相关文章

第一阶段:Java内功秘籍-线性表

前言 为什么要学习数据结构与算法,如果你学会了做安卓,javaweb,前端等,都是你的武功秘籍,但是如果你的内功不够好,再厉害的功夫也是白费. 数据结构和算法:什么是数据结构,什么是数据,在计算机内部数据为01010101...,数据是我们生活中一切的事务都可以表示为数据,如你和你朋友聊天的话都是数据,朋友圈的发表内容也是内容. 数据结构是数据之间相互存在的一种或多种特定的关系,数据之间的关系.数据结构的关系,要么一对一,或者一对多. er图,实体关联图.数据与数据之间的关系,分: 图形结构 树

C++数据结构与算法_2_线性表 --顺序表的应用示例

h2.western { font-family: "Liberation Sans",sans-serif; font-size: 16pt; }h2.cjk { font-family: "微软雅黑"; font-size: 16pt; }h2.ctl { font-family: "AR PL UMing CN"; font-size: 16pt; }h1 { margin-bottom: 0.21cm; }h1.western { fon

C++数据结构与算法_1_线性表 --顺序表的实现与分析

顺序表的实现与分析 引 --线性表的抽象基类: template <typename T> class LinearList { public: LinearList(); ~LinearList(); virtual int Size() const = 0; //返回线性表所能够存储的最大长度 virtual int Length() const = 0; //当前线性表的长度 virtual int Search(T &x) const = 0; virtual int Loca

2、蛤蟆的数据结构笔记之二线性表

2.蛤蟆的数据结构笔记之二线性表 到了笔记二了,每个笔记开头都应该弄个语句激励一下自己和小伙伴. "人生中最重要的不是位置,而是前进的方向" 这次咱们学习表,没错是表.什么表?额,汉字真是博大精深,没错,只是个表.不要想歪了. 欢迎转载,转载请标明出处: 1.  定义 线性表(亦作顺序表)是最基本.最简单.也是最常用的一种数据结构.线性表中数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的.线性表的逻辑结构简单,便于实现和操作.因此,线性表

javascript实现数据结构: 稀疏矩阵之三元组线性表表示

稀疏矩阵(Sparse Matrix):对于稀疏矩阵,目前还没有一个确切的定义.设矩阵A是一个n*m的矩阵中有s个非零元素,设  δ=s/(n*m),称δ为稀疏因子, 如果某一矩阵的稀疏因子δ满足δ≦0.05时称为稀疏矩阵, 稀疏矩阵的压缩存储 对于稀疏矩阵,采用压缩存储方法时,只存储非0元素.必须存储非0元素的行下标值.列下标值.元素值.因此,一个三元组(i, j, aij)唯一确定稀疏矩阵的一个非零元素. 上图的稀疏矩阵A的三元组线性表为: ( (1,2,12), (1,3,9), (3,1

数据结构(二)——线性表简介

数据结构(二)--线性表简介 一.线性表简介 1.线性表简介 线性表是具有相同类型的n个数据元素的有限序列A0,A1,A2,...,An-1.Ai是表项,n是表的长度. 2.线性表的表现形式 线性表的表现形式:A.零个或多个数据元素组成的集合B.数据元素在位置上是有序排列的C.数据元素的个数是有限的D.数据元素的类型必须相同 3.线性表的性质 线性表的性质:A.A0为线性表的第一个元素,只有一个后继B.An-1为线性表的最后一个元素,只有一个前驱C.除A0与An-1外的其它元素既有前驱又有后继D

Java数据结构与算法(1):线性表

线性表是一种简单的数据类型,它是具有相同类型的n个数据元素组成的有限序列.形如如A0,A1,...,An-1.大小为0的表为空表,称Ai后继Ai-1,并称Ai-1前驱Ai. printList打印出表元素,makeEmpty置空表,find返回某一项首次出现的位置,insert和remove一般是从表的某个位置插入和删除某个元素:而findKth则返回某个位置上的元素,next和previous会取一个位置作为参数返回前驱元和后继元的值. 表的数组实现 对表的所有操作都可以通过数组实现.数组的存

数据结构Java实现02----线性表与顺序表

[正文] 本节内容: 线性结构 线性表抽象数据类型 顺序表 顺序表应用 一.线性结构: 如果一个数据元素序列满足: (1)除第一个和最后一个数据元素外,每个数据元素只有一个前驱数据元素和一个后继数据元素: (2)第一个数据元素没有前驱数据元素: (3)最后一个数据元素没有后继数据元素. 则称这样的数据结构为线性结构. 二.线性表抽象数据类型: 1.线性表抽象数据类型的概念: 线性表抽象数据类型主要包括两个方面:既数据集合和该数据集合上的操作集合. 数据集合: 可以表示为a0,a1,a2,...a

数据结构(C++)&mdash;&mdash;线性表

线性表在数据结构中的基础章节,通过线性表的学习可以让我们对数据结构有一个基本的认识.下面是我对线性表的一些理解. 首先线性表的学习可以概括为三点: 数据描述. 数据存储. 数据操作. 1.数据描述 线性表的数据元素具有抽象(及不确定)的数据类型,只有在设计具体的应用程序时,数据元素的抽象类型将被具体的数据类型所取代,比如:字符型(char).整型(int).结构体类型(struct)等等.下面我就把一张成绩表用结构体类型描述出来. 如图,如何将这这些数据封装为一个数据类型呢?C++中用的是类(c