数据结构:这是一份全面& 详细的 线性表 学习指南

前言

  • 本文主要讲解 数据结构中最基础的线性表
  • 内容包括其特点、结构(顺序存储结构 & 链式结构)等,希望你们会喜欢。

1. 简介

  • 其中,线性表的存储结构最为重要 下面,我将主要讲解其 顺序存储结构 & 链式存储结构

2. 顺序存储结构

  • 实现方式:数组
  • 下面,我将主要讲解其结构特点 & 相关操作

2.1 结构特点

  1. 存储线性表的数据元素的方式 = 一段地址连续的存储单元
  2. 具备:起始位置、数组长度(最大存储容量) & 线性表长度(当前长度)
  • 示意图
  • 概念说明

概念

说明

数组长度

存放线性表的空间长度(固定不变)

线性表长度

存放线性表数据元素的长度(动态变化)

地址

存储单元的编号

数组下标

第 i 个元素 = 数组下标第 i-1 的位置

2.2 对应操作

顺序存储结构的操作包括:插入 & 删除

  • 操作1:插入
  • 操作2: 删除

注:线性表的存取数据时间性能 = O(1)

2.3 结构优、缺点

2.4 应用场景

已知长度、数据元素个数变化不大、存、取数据频率高的场景

2.5 总结


3. 链式存储结构

  • 实现方式:链表
  • 下面,我将主要讲解其结构特点 & 相关操作

3.1 结构特点

  • 链表示意图(以单链表为例)
  • 存储元素说明示意图

下面将主要重点讲解各种链表:(重点讲解)单链表、双向链表、循环链表、静态链表

3.2 单链表

3.2.1 定义

每个结点只有1个指针域

3.2.2 示意图
3.2.3 操作(读取、插入、删除、整表创建、整表删除)
  • 读取 算法思路:工作指针向后移
int j ;

// 1. 声明1动态指针
LinkList p ; 

// 2. 让p指向链表L的第一个结点
// L = 头结点
p = L ->next

// 3. 设置计数器
j = 1;
while ( p && j<i ){

p = p->next;// 指向下一个结点
++j;

}

// 直到到了i结点,直接取出
e = p->data
  • 插入

通过遍历找到i结点,生成一个空结点,然后插入

  • 删除
  • 整表创建
  • 整表删除
  • 单链表实现

http://blog.csdn.net/chenleixing/article/details/42392283

public class UnidirectionalLinkedList<T> {

    /**
     * 设置结点结构
     */
    // a. 结点结构
    private class Node<T>{
        private T data;
        private Node<T> next ;
        public Node(T data){
            this.data = data;
        }
    }

    // b. 头结点
    private Node<T> first;
    // c. 当前结点
    private Node<T> currentNode;
    // d. 链表长度
    private int size;

    /**
     * 构造函数
     * 作用:初始化结点
     */
    public UnidirectionalLinkedList(){
        currentNode = first = null;
        size = 0;
    }

    /**
     * 1. 添加结点
     * 内容:在头 / 尾 添加结点 & 在特定位置插入结点
     */

    // a. 在链表头部加入1个结点
    // 即,把新加入的结点设置为第一结点
    public void addFirstNode(T data){

        // 1. 将需添加的内容封装成结点
        Node<T> newNode = new Node<T>(data);
        // 2. 将新添加结点的指针域指向旧第1个结点
        newNode.next = first;
        // 3. 将新添加结点设置为第1个结点
        first = newNode;
        // 4. 链表长度+1
        size++;
    }

    // b. 在链表尾部加入1个结点
    // 即,把新加入的结点设置为最后结点
    public void addNode(T data){
        // 1. 检查当前链表是否为空
        if (isEmpty()){
            addFirstNode(data);
            return;
        }
        // 2. 把当前指针定位到最后一个结点
        locateNode(size-1);
        // 3. 将需添加的内容封装成结点
        currentNode.next = new Node<T>(data);
        // 4. 链表长度+1
        size++;
    }

    // c. 在链表中插入结点
    public T insertNode(int index, T data) {
        // 1. 检查当前链表是否为空
        if (isEmpty()){
            addFirstNode(data);
            return null;
        }

        // 2. 把当前指针定位到需插入的结点位置
        locateNode(index);
        // 3. 将需添加的内容封装成结点
        Node<T> insertNode = new Node<T>(data);
        // 4. 把需插入结点位置的下1个结点 赋给 插入的结点
        insertNode.next = currentNode.next;
        // 5. 把插入结点 赋给 需插入的结点的位置
        currentNode.next = insertNode;
        // 6. 链表长度+1
        size++;
        // 7. 返回插入结点的数据
        return insertNode.data;
    }


    /**
     * 2. 删除结点
     * 内容:删除第1个结点 & 删除特定位置的结点
     */
    // a. 删除第1个结点,并返回该结点数据
    public T removeFirstNode()  {
        // 1. 检查当前链表第一个结点是否为空
        if (first == null){
            try {
                throw new Exception("链表为空!");
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
        // 2. 获取被删除结点的数据
        T temp = first.data;
        // 3. 将第2个结点设置为第1个结点
        first = first.next;
        // 4. 链表长度减1
        size--;

        // 5. 返回被删除结点的数据
        return temp;
    }


    // b. 删除特定位置的结点,并将里面的数据返回
    public T removeNode(int index)  {
        // 1. 检查当前链表是否为空
        if (isEmpty()){
            try {
                throw new Exception("链表为空!");
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
        // 2. 把当前指针(currentNode)定位到 需删除结点(index)的前1个结点
        locateNode(index-1);
        // 3. 获取被删除结点的数据
        T temp = currentNode.next.data;
        // 4. 将需删除结点(index)的前1个结点 的下1个结点 设置为 需删除结点(index)的下1个结点
        currentNode.next = currentNode.next.next;
        // 5. 链表长度减1
        size--;
        // 6. 返回被删除结点的数据
        return temp;
    }

    /**
     * 3. 获取特定位置的结点
     * 内容:将当前指针(currentNode)定位到所需结点位置、根据索引位置获取结点数据
     */

    // a. 将当前指针(currentNode)定位到所需结点位置
    private void locateNode(int index){
        // 1. 判断指针是否越界
        if (index <0 && index >size){
            try {
                throw new IndexOutOfBoundsException("参数越界!");
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
        int i = 0;
        // 2. 通过遍历链表,寻找索引index所指结点
        for(currentNode = first; currentNode.next != null && i < index; i++){
            currentNode = currentNode.next;
        }
    }

    // b. 根据索引位置获取结点数据
    public T getNode(int index)  {
        // 1. 判断链表是否为空
        if (isEmpty()){
            try {
                throw new Exception("链表为空!");
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
        // 2. 把当前指针(currentNode)定位到 所需索引位置(index)
        locateNode(index);
        // 3. 返回当前指针的数据,即所需索引位置的数据
        return currentNode.data;
    }

    /**
     * 检查当前链表是否为空
     */
    public boolean isEmpty(){
        if (size == 0){
            return true;
        }else {
            return false;
        }
    }


    public static void main(String[] args){
        // 1. 创建链表 & 加入结点数据
        UnidirectionalLinkedList<Integer> list = new UnidirectionalLinkedList<Integer>();
        list.addNode(1);
        list.addNode(2);
        list.addNode(3);
        list.addNode(4);
        list.addNode(5);

        // 2. 输出当前链表数据
        System.out.println("链表数据如下:");
        for (int i = 0; i < list.size;i++){
            
            try {

                System.out.print(list.getNode(i)+" ");
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
        System.out.println("-----------------------");


        // 3. 获得某个位置结点的数据
        System.out.println("位置3的数据是:" + list.getNode(3));


        System.out.println("-----------------------");


        // 4. 插入结点:在位置4插入,数据 = 66
        System.out.println("在位置4插入的data:"+list.insertNode(3,66));
        System.out.println("插入后:");
        for (int i = 0; i < list.size;i++){
            try {
                System.out.print(list.getNode(i)+" ");
            } catch (Exception e) {
                e.printStackTrace();
            }
        }

        System.out.println("-----------------------");

        // 5. 删除结点
        System.out.println("删除index为3的data:"+list.removeNode(3));
        System.out.println("删除后:");
        for (int i = 0; i < list.size;i++){
            try {
                System.out.print(list.getNode(i)+" ");
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
    }


}
  • 测试结果
链表数据如下:1 2 3 4 5 
-----------------------
位置3的数据是:4
-----------------------
在位置4插入的data:66
插入后:1 2 3 4 66 5 
-----------------------
删除index为3的data:4
删除后:1 2 3 66 5

3.3 循环链表

  • 定义 将单链表的终端结点的指针指向头结点、使得单链表头尾相接、形成1个环

也称单循环链表

  • 示意图

3.4 双向链表

3.4.1 定义

每个结点有2个指针域:1指向后驱结点元素、2指向前驱结点元素

即 在单链表的结点中,再设置一个指向前驱结点的指针域

3.4.2 示意图

3.4.3 链表操作(插入& 删除)

注:插入 & 删除都需要同时改变2个指针变量

3.4.4 特点

  • 缺点:占用空间多 = 记录2个指针
  • 优点:算法时间性能高 = 良好对称性(前、后指针)

即,用空间换时间

3.5 静态链表


4. 存储结构对比


5. 总结

  • 本文主要讲解了数据结构中最基础的线性表
  • 下面我将继续对 数据结构,有兴趣可以继续关注Carson_Ho的安卓开发笔记

请帮顶 / 评论点赞!因为你的鼓励是我写作的最大动力!

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券