什么是线性表、顺序表、链表

发布时间:2021-10-13 10:35:50 作者:iii
来源:亿速云 阅读:109

本篇内容介绍了“什么是线性表、顺序表、链表”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!

首先来看一下线性表,顺序表,和链表之间的区别和联系:

  1. 逻辑结构, 就是对外暴露数据之间的关系,不关心底层如何实现,数据结构的逻辑结构大分类就是线性结构和非线性结构,而顺序表、链表都是一种线性表。

  2. 线性表结构存储的数据往往是可以依次排列的,就像小朋友手拉手,每位学生的前面和后面都仅有一个小朋友和他拉手,具备这种“一对一”关系的数据就可以使用线性表来存储。

线性表

我们首先定义一个线性表的抽象类,主要包括增加、查找、删除等方法。后面分别用顺序表和链表做实现:

/**
 * 线性表
 *
 * @author ervin
 * @Date 2021/4/18
 */
public interface ListInterface<T> {

    /**
     * 初始化
     * @param size
     */
    void init(int size);

    /**
     * 长度
     * @return
     */
    int length();


    /**
     * 是否为空
     * @return
     */
    boolean isEmpty();

    /**
     * 获取元素下标
     * @param t
     * @return
     */
    int eleIndex(T t);

    /**
     * 根据index获取数据
     * @param index
     * @return
     * @throws Exception
     */
    T getEle(int index) throws Exception;

    /**
     * 根据index插入数据
     * @param index
     * @param t
     * @throws Exception
     */
    void add(int index,T t) throws Exception;

    /**
     * 删除元素
     * @param index
     * @throws Exception
     */
    void delete(int index) throws Exception;

    /**
     * 尾部插入元素
     * @param t
     * @throws Exception
     */
    void add(T t) throws Exception;

    /**
     * 修改
     * @param index
     * @param t
     * @throws Exception
     */
    void set(int index,T t) throws Exception;
}

顺序表

顺序表元素插入示意图:

什么是线性表、顺序表、链表

这里以插入为例做说明,删除操作正好相反。

代码实现:

/**
 * 顺序表实现
 *
 * @author ervin
 * @Date 2021/4/18
 */
public class SeqList<T> implements ListInterface<T> {

    //数组存放数据
    private Object[] date;

    private int length;

    public SeqList() {
        //初始大小默认为10
        init(10);
    }

    @Override
    public void init(int initSize) {
        this.date = new Object[initSize];
        length = 0;
    }

    @Override
    public int length() {
        return this.length;
    }

    @Override
    public boolean isEmpty() {
        //是否为空
        return this.length == 0;
    }


    @Override
    public int eleIndex(T t) {
        for (int i = 0; i < date.length; i++) {
            if (date[i].equals(t)) {
                return i;
            }
        }
        return -1;
    }


    @Override
    public T getEle(int index) throws Exception {
        if (index < 0 || index > length - 1) {
            throw new Exception("数值越界");
        }
        return (T) date[index];
    }

    @Override
    public void add(T t) throws Exception {
        //尾部插入
        add(length, t);
    }


    @Override
    public void add(int index, T t) throws Exception {
        if (index < 0 || index > length) {
            throw new Exception("数值越界");
        }
        //扩容
        if (length == date.length) {
            Object[] newDate = new Object[length * 2];
            for (int i = 0; i < length; i++) {
                newDate[i] = date[i];
            }
            date = newDate;
        }
        //后面元素后移动
        for (int i = length - 1; i >= index; i--) {
            date[i + 1] = date[i];
        }
        //插入元素
        date[index] = t;
        length++;

    }

    @Override
    public void delete(int index) throws Exception {
        if (index < 0 || index > length - 1) {
            throw new Exception("数值越界");
        }
        //index之后元素前移动
        for (int i = index; i < length; i++) {
            date[i] = date[i + 1];
        }
        length--;
    }

    @Override
    public void set(int index, T t) throws Exception {
        if (index < 0 || index > length - 1) {
            throw new Exception("数值越界");
        }
        date[index] = t;
    }
}

链表

如图:

什么是线性表、顺序表、链表

链表元素插入示意:

什么是线性表、顺序表、链表

链表元素删除示意图:

什么是线性表、顺序表、链表

代码实现:

/**
 * 链表实现
 *
 * @author ervin
 * @Date 2021/4/18
 */
public class LinkList<T> implements ListInterface<T> {


    private static class Node<T> {
        T item;
        Node<T> next;

        Node(T element, Node<T> next) {
            this.item = element;
            this.next = next;
        }
    }

    Node header;

    private int size;

    public LinkList(){
        this.header = new Node(null,null);
        this.size = 0;
    }

    @Override
    public void init(int size) {
    }

    @Override
    public int length() {
        return this.size;
    }

    @Override
    public boolean isEmpty() {
        return this.length() == 0;
    }

    @Override
    public int eleIndex(T t) {
        Node n = header.next;
        int index = 0;
        while (n.next != null){
            if (n.item.equals(t)){
                return index;
            }
            index++;
            n = n.next;
        }
        //找不到返回-1
        return -1;
    }

    @Override
    public T getEle(int index) throws Exception {
        Node n = getNode(index);
        return (T)n.item;
    }

    @Override
    public void add(int index, T t) throws Exception {
        //考虑第一个元素
        if (index == 0){
            this.header.next = new Node(t,null);
        } else {
            Node n = getNode(index - 1);
            //获取到index的上一个元素n, n指向新建的元素,同时新建的元素指向n的下一个元素
            n.next = new Node(t,n.next);
        }
        this.size++;
    }

    @Override
    public void delete(int index) throws Exception {
        //index为0时,不用去获取上一个元素,
        if (index == 0){
            this.header.next = getNode(1);
        } else {
            Node n = getNode(index - 1);
            n.next = n.next.next;
        }
        size--;
    }

    @Override
    public void add(T t) throws Exception {
        add(size,t);
    }

    @Override
    public void set(int index, T t) throws Exception {
        Node node = getNode(index);
        node.item = t;
    }

    private Node getNode(int index) throws Exception {
        if (index<0 || index > this.size-1){
            throw new Exception("数组越界");
        }
        Node n = header.next;
        for (int i = 0;i<index;i++){
            n = n.next;
        }
        return n;
    }
}

双链表

在实际应用中双链表的应用多一些,就比如LinkedList

双链表的一个节点,有存储数据的data,也有后驱节点next(指针),指向下一个节点,这和单链表是一样的,但它还有一个前驱节点pre(指针),指向上一个节点。

什么是线性表、顺序表、链表

这一点,在 JDK LinkedList 的源码中有体现,我们来看它的 get(int index) 方法,

什么是线性表、顺序表、链表

接着点进去,看它的 node(int index) 方法

什么是线性表、顺序表、链表

如果 index 位于链表的前半部分,则从前开始查找;反之,则从后开始查找。

总结

“什么是线性表、顺序表、链表”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识可以关注亿速云网站,小编将为大家输出更多高质量的实用文章!

推荐阅读:
  1. 数据结构线性表(顺序表,单链表)
  2. c#线性表中链表怎么用

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

java php

上一篇:PHP如何实现自排序二叉树

下一篇:基于PHP如何对XML进行操作

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》