数据结构-线性表-JAVA描述

小灰灰 2022-09-26 03:18 133阅读 0赞

## 前言 ##

此时，我是计算机专业大四学生，这是我第一篇博客。写技术博客，不仅仅是为了写给别人看，同时也是对自己所学的知识进行整理。写博客的过程，是对已经掌握的知识进行回忆，发散思维，联想到更多的知识的一个过程，同时慢慢梳理知识网络。
    我的第一篇博客，就写写数据结构中的线性表

**定义**

在线性表中可以存一组数，或者一组元素，这里指的元素是指数据元素，可以由若干个数据项组成，例如：
    
    线性表是常用的且最简单的一种数据结构，特点是：
    1.线性表中必须存在并且只有一个称为“第一个元素”的元素
    2.线性表中必须存在并且只有一个称为“最后一个元素”的元素
    3.除第一个元素外，每个元素有且仅有一个前驱
    4.除最后一个元素外，每个元素有且仅有一个后继

## 顺序表 ##

在JAVA中，顺序表可以用数组实现，JAVA里数组在内存中的存放方式是用一段物理地址连续的存储空间存放的。String类型的对象也是用数组来存放，所以String类型的对象也是以顺序表的方式来存储。也可以用ArrayList类型变量来存储，它也是以顺序表的方式存放的。
    顺序表的特点是随机存储，这样在更利于数据的访问。顺序表的物理实现直接反映了逻辑映像。但是对顺序表做增删元素操作，会消耗较多的资源，因为要求逻辑关系相等的两个元素其物理位置也要相邻，那么在删除/增加一个元素的时候，该位置之后的元素要全部逐个往前/往后移动一个位置。

//创建一个顺序表
    List<Integer> list = new ArrayList<Integer>();

//插入操作：往list末尾插入A,C,D,E
            list.add("A");
            list.add("C");
            list.add("D");
            list.add("E");
            //在第一个位置(A和C之间插入B)
            list.add(1, "B");

/*
             * 删除操作:删除list中指定位置的元素，这个元素之后的元素都将往前移动一个位置
             * 时间复杂度为O(list.size()-i-1) i为删除的元素的原位置 
             * 删除第0个元素 A
             */
            list.remove(0);

//经过以上操作后，输出结果为：BCDE
            for (String string : list) {
                System.out.print(string);
            }

/* * 查询操作：获取list中指定位置的元素 * 经过以上操作后，输出结果为：B */
            System.out.println(list.get(0));

/*
             * 截取一个list的子list
             * 截取list中的从0(包括)开始到3(不包括)的元素
             * 注意：新顺序表是对原顺序表中子串的引用，对子串中元素的修改，也是对原顺序表中对应元素的修改
             * 输出结果为BCD
             */
            List<String> childList = list.subList(0, 3);
            for (String string : childList) {
                System.out.print(string);
            }

/* * 将数组转换为List * List元素的类型为数组元素的类型 * 注意：不能增删转换后的List集合的元素，否则会抛出异常，因为List是对原数组的引用 * 输出结果为abcde */
            String[] str = new String[]{
       "a","b","c","d","e"};
            List<String> charList = Arrays.asList(str);
            for (String string : charList) {
                System.out.print(string);
            }
            //charList.add("t"); 将抛出异常

--------------------

## 链表 ##

链表是线性表在内存中的另一种实现方式，它用一组在内存中不连续的存储单元来存放数据，这跟上述的线性表相反。
    链表中，每个元素成为**结点**，每个结点由两个部分组成，数据区和指针区，数据区存放的是这个结点存放的数据，指针区存放的则是指向这个结点所存元素的下一个元素（逻辑关系上的）指针。
    以这种方式存储数据，相比顺序表，优点是在做对表的增删操作时，不需要消耗更多的资源。要删除元素时，只要将指针区的指针指向修改后的元素的地址，就实现了增删操作。在插入元素时，只要将要插入的位置的上一个结点的指针指向这个元素，新插入的结点的指针指向之前结点指向的元素，即可。但是以这种方式存储，在对线性表进行查询操作的时候，便失去了顺序表随机存取的优点，例如要查询第i个元素，则要从链表的第一个元素开始查找，直到第i个位置。
    
    在JAVA中，可以用LinkedList类来实现线性表的链式存储。

//创建一个链表
    List<Integer> list = new LinkedList<Integer>;

我们对链表的操作方式跟顺序表的操作方式相同，只是内部实现不一样，便不再重述。