Web全栈~22.数据结构(线性表)

上一期

前言

       数据结构系列的博客,我过去也有写过,但那都是基于C语言。接下来几期关于数据结构的博客则会使用Java来实现。数据结构的逻辑概念就不重复说了,这里提供以前写过的博客链接。

       顺序表采用一组地址连续的存储单元依次存放数据元素，通过元素之间的先后顺序来确定元素 之间的位置，因此存储空间的利用率较高

       单链表采用一组地址任意的存储单元来存放数据元素，通过存储下一个节点的地址值来确定节 点之间的位置，因此存储空间的利用率较低。

存储方式比较

       顺序表查找的时间复杂度为 O(1)，插入和删除需要移动元素，因此时间复杂度为 O(n)。若是需 要频繁的执行查找操作，但是很少进行插入和删除操作，那么建议使用顺序表。

       单链表查找的时间复杂度为 O(n)，插入和删除无需移动元素，因此时间复杂度为 O(1)。若是需 要频繁的执行插入和删除操作，但是很少进行查找操作，那么建议使用链表。

相关博客

线性表的基本实现和概念

顺序表的操作

---

ArrayList

       关于线性表的基本概念,上面已经提供了链接。我们知道线性表的存储结构有顺序存储结构和链式存储结构,顺序存储结构被称为顺序表。链式存储结构被称为链表。

       而ArrayList则就是一种类似顺序表的数据结构。

       ArrayList底层是使用数组作为容器存储数据,不同于数组的是,ArrayList的内存长度是动态变化的,而数组的长度一旦确定好了之后就无法再改变。因此,存储不确定大小数据的时候,使用ArrayList比使用数组会更加方便。

ArrayList接口

package arraylist.List;

import arraylist.iterator.Iterator;

public interface List <T>{
    // ------- 添加 -------
    void add(Object object);

    // ------- 根据坐标删除 -------
    void remove(int index);

    // ------- 根据内容删除 -------
    void removeobj(Object object);

    // ------- 取出数据 -------
    Object get(int index);

    // ------- 求集合的长度 -------
    int size();

    // ------- 判断集合是否为空 -------
    boolean isEmpty();

    // ------- 根据内容找到元素坐标 -------
    int IndexOf(Object object);

    // ------- 判断元素是否存在 -------
    boolean contions(Object object);

    // ------- 根据坐标位置插入元素 -------
    void add(int index, Object object);

    // ------- 修改元素 -------
    void replase(int index, Object object);

    // ------- toString -------
    String toString();

    // ------- arraylist迭代器 -------
    Iterator iterator();
}

Iterator接口

public interface Iterator <T>{
    boolean hasNext();
    T next();
}

ArrayList实现类

public class ArrayList <T>implements List {
    public Object []elementData;       //数组的引用
    private int size;                   //集合的大小，并非elementData.length
    //如果用户没设置大小就初始为10
    public ArrayList(){
        this(10);       //数组大小初始为10
    }
    //集合的大小等于用户设置的大小
    public ArrayList(int len){
        elementData = new Object[len];
    }

    // 数组的扩容
    void grow(){
        //创建新的数组
        Object []newArr = new Object[elementData.length + (elementData.length >> 1)];//扩容1.5倍
        for(int i = 0; i < size; i++){
            //将原来数组的内容存到新数组里
            newArr[i] = elementData[i];
        }
        elementData = newArr;
    }
    //在集合的尾部添加元素
    public void add(Object object) {
        //如果数组长度不够就调用扩容
        if(elementData.length <= size){
            grow();
        }
        elementData[size] = object;
        //大小增加一位
        size++;
    }
    //根据坐标删除元素
    public void remove(int index) {
        //判断用户是否输入错误
        if(index<0|| index >size-1){
            throw  new IndexOutOfBoundsException("索引越界"+index);
        }
        Object element=elementData[index];
        // 向前移动元素
        for (int i = index; i <size-1 ; i++) {
            elementData[i]=elementData[i+1];
        }
        // 最后一个元素置为空
        elementData[size-1]=null;
        size--;
    }
    //根据元素删除
    public void removeobj(Object object) {
        int index = IndexOf(object);
        //判断用户是否输入错误!
        if(index<0){
            throw new NullPointerException();
        }
        remove(index);
    }
    //根据坐标得到元素
    public Object get(int index) {
        return elementData[index];
    }
    //求集合的长度
    public int size() {
        return size;
    }
    //判断是否为空
    public boolean isEmpty() {
        return size == 0;
    }
    //根据元素找到坐标
    public int IndexOf(Object object) {
        int i = 0;
        while(i < size){
            if(elementData[i].equals(object)){
                break;
            }
            i++;
        }
        return i;
    }
    //判断元素是否存在
    public boolean contions(Object object) {
        boolean flag = false;
        for(int i = 0; i < size; i++){
            if(elementData[i].equals(object)){
                flag = true;
                break;
            }
        }
        return flag;
    }
    //根据坐标位置添加元素
    public void add(int index, Object object) {
        if(size >= elementData.length){
            grow();
        }
        for(int i = size; i > index; i--){
            elementData[i] = elementData[i - 1];
        }
        elementData[index] = object;
        size++;
    }
    //修改元素
    public void replase(int index, Object object) {
        elementData[index] = object;
    }
    //重写toString
    public String toString(){
        StringBuilder str = new StringBuilder("[");
        for(int i = 0; i < size; i++){
            //判断是否到了最后一位,如果到了就不添加,
            if(i == size - 1){
                str.append(elementData[i]);
                break;
            }else{
                str.append(elementData[i] + ",");
            }
        }
        str.append("]");
        return str.toString();
    }

    // ------- 迭代器 -------
    public Ite iterator(){
        return new Ite();
    }

    private class Ite<T>implements Iterator<T> {
        int cursor = 0; //指向当前元素，默认是0
        public ArrayList arr = new ArrayList();

        public boolean hasNext() {
            return cursor != size;
        }

        public T next() {
            int i = cursor; //保留当前值
            cursor++;//自增
            // 进行判断，防止越界
            if (i > size) {
                throw new RuntimeException("没有元素");
            }
            return (T) elementData[i];
        }
    }
}

测试

 List list = new ArrayList();
 //增加测试
 for(int i = 1; i < 19; i++){
     list.add(i);
 }
 list.add(9,564);
 //迭代器测试
 Iterator iterator = list.iterator();
 while(iterator.hasNext()){
     System.out.print(iterator.next() + " ");
 }
 //其他方法测试
 System.out.println("是否为空: " + list.isEmpty());
 System.out.println("长度: " + list.size());
 System.out.println("元素 15 是否存在: " + list.contions(15));
 System.out.println("元素 564的坐标: " + list.IndexOf(564));
 System.out.println("将坐标3元素 改成 23: "); list.replase(3,23);
 System.out.println("取出坐标7: " + list.get(7));
 System.out.println("删除坐标5: " );  list.remove(5);
 System.out.println("删除元素 564: "); list.removeobj(564);
 //最后toString
 System.out.println(list.toString());

---

LinkedList

       链表也是线性表的一种存储方式,我们称之为链式存储

相关博客

关于单链表的归并以及头尾插入问题

单链表的增删查改

双链表

关于线性表的两个案例

单链表Java实现

定义List接口

public interface List {
    int size();
    void add(Object element);
    Object get(int index);
    void remove(int index);
    void add(int index, Object element);
    String toString();
}

SingleLinkedList实现类

public class SingleLinkedList implements List{
     // 用于保存单链表中的首节点
    private Node headNode;

    // 用于保存单链表中的尾节点
    private Node lastNode;

   // 用于保存单链表中节点的个数
    private int size;

     // 获取单链表中节点的个数
    public int size() {
        return this.size;
    }
    /**
     * 添加元素
     * @param element 需要添加的数据
     */
    public void add(Object element) {
        // 1.把需要添加的数据封装成节点对象
        Node node = new Node(element);
        // 2.处理单链表为空表的情况
        if(headNode == null) {
            // 2.1把node节点设置为单链表的首节点
            headNode = node;
            // 2.2把node节点设置为单链表的尾节点
            lastNode = node;
        }
        // 3.处理单链表不是空表的情况
        else {
            // 3.1让lastNode指向node节点
            lastNode.next = node;
            // 3.2更新lastNode的值
            lastNode = node;
        }
        // 4.更新size的值
        size++;
    }

    /**
     * 根据序号获取元素
     * @param index 序号
     * @return 序号所对应节点的数据值
     */
    public Object get(int index) {
        // 1.判断序号是否合法，合法取值范围：[0, size - 1]
        if(index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("序号不合法，index:" + index);
        }
        // 2.根据序号获得对应的节点对象
        Node node = node(index);
        // 3.获取并返回node节点的数据值
        return node.data;
    }

    /**
     * 根据序号删除元素
     * @param index 序号
     */
    public void remove(int index) {
        // 1.判断序号是否合法，合法取值范围：[0, size - 1]
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("序号不合法，index:" + index);
        }
        // 2.处理删除节点在开头的情况
        if (index == 0) {
            // 2.1获得删除节点的后一个节点
            Node nextNode = headNode.next;
            // 2.2设置headNode的next值为null
            headNode.next = null;
            // 2.3设置nextNode为单链表的首节点
            headNode = nextNode;
        }
        // 3.处理删除节点在末尾的情况
        else if (index == size - 1) {
            // 3.1获得删除节点的前一个节点
            Node preNode = node(index - 1);
            // 3.2设置preNode的next值为null
            preNode.next = null;
            // 3.3设置preNode为单链表的尾节点
            lastNode = preNode;
        }
        // 4.处理删除节点在中间的情况
        else {
            // 4.1获得index-1所对应的节点对象
            Node preNode = node(index - 1);
            // 4.2获得index+1所对应的节点对象
            Node nextNode = preNode.next.next;
            // 4.3获得删除节点并设置next值为null
            preNode.next.next = null;
            // 4.4设置preNode的next值为nextNode
            preNode.next = nextNode;
        }
        // 5.更新size的值
        size--;
    }

    /**
     * 根据序号插入元素
     * @param index 序号
     * @param element 需要插入的数据
     */
    public void add(int index, Object element) {
        // 1.判断序号是否合法，合法取值范围：[0, size]
        if(index < 0 || index > size) {
            throw new IndexOutOfBoundsException("序号不合法，index:" + index);
        }
        // 2.把需要添加的数据封装成节点对象
        Node node = new Node(element);
        // 3.处理插入节点在开头位置的情况
        if(index == 0) {
            // 3.1设置node的next值为headNode
            node.next = headNode;
            // 3.2设置node节点为单链表的首节点
            headNode = node;
        }
        // 4.处理插入节点在末尾位置的情况
        else if(index == size) {
            // 4.1设置lastNode的next值为node
            lastNode.next = node;
            // 4.2设置node节点为单链表的尾节点
            lastNode = node;
        }
        // 5.处理插入节点在中间位置的情况
        else {
            // 5.1获得index-1所对应的节点对象
            Node preNode = node(index - 1);
            // 5.2获得index所对应的节点对象
            Node curNode = preNode.next;
            // 5.3设置preNode的next为node
            preNode.next = node;
            // 5.4设置node的next为curNode
            node.next = curNode;
        }
        // 6.更新size的值
        size++;
    }

    /**
     * 根据序号获得对应的节点对象
     * @param index 序号
     * @return 序号对应的节点对象
     */
    private Node node(int index) {
        // 1.定义一个零时节点，用于辅助单链表的遍历操作
        Node tempNode = headNode;
        // 2.定义一个循环，用于获取index对应的节点对象
        for(int i = 0; i < index; i++) {
            // 3.更新tempNode的值
            tempNode = tempNode.next;
        }
        // 4.返回index对应的节点对象
        return tempNode;
    }

  
    // 节点类

    private static class Node {
        /**
         * 用于保存节点中的数据
         */
        private Object data;
        /**
         * 用于保存指向下一个节点的地址值
         */
        private Node next;
        /**
         * 构造方法
         * @param data
         */
        public Node(Object data) {
            this.data = data;
        }
    }

    public String toString() {
        //判断是否为空,如果为空就直接返回 []
        if(headNode == null){
            return "[]";
        }
        StringBuilder stringBuilder = new StringBuilder("[");
        Node p = headNode.next;
        while(p != null){
            stringBuilder.append(p.data + ",");
            p = p.next;
        }
        //最后一个逗号删掉
        stringBuilder.deleteCharAt(stringBuilder.length()-1);
        stringBuilder.append("]");
        return stringBuilder.toString();
    }
}

双链表Java实现

定义List接口

public interface List <E>{
    int size();
    boolean isEmpty();
    boolean contains(E element);
    void add(E element);
    E get(int index);
    E set(int index,E element);
    void add(int index,E element);
    E remove(int index);
    int indexOf(E element);
    void clear();
    String toString();
}

接口实现

public class LinkedList<E> implements List<E>{

    private int size;   //集合的长度
    private Node first;
    private Node last;

    @Override
    public int size() {
        return size;
    }

    //判断当前集合中是否有元素
    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    //判断当前元素是否存在
    @Override
    public boolean contains(E element) {
        return indexOf(element) > -1;
    }

    @Override
    public void add(E element) {
        //调用下面的add方法,根据size保证每次都添加在最后
        add(size,element);
    }
    //取得坐标位置上的节点
    private Node<E> node(int index){
        Node N = first; //指向头
        //先判断要查找的index,是靠近头还是靠近尾
        //如果靠近头就从头开始查找,如果靠近尾就从尾开始查找
        //方法: 根据index 和 size的一半去比较
        if(index > (size >> 1)){
            //靠近尾
            N = last;   //指向尾
            for(int i = size-1; i > index; i--){
                N = N.pre;
            }
        }else{
            //靠近头
            for(int i = 0; i < index; i++){
                N = N.next;
            }
        }
        return N;
    }

    @Override
    public E get(int index) {
        //防止坐标越界
        if(index < 0 || index >= size){
            throw  new IndexOutOfBoundsException("index： " + index + " size: " + size);
        }
        //调用方法
        return node(index).element;
    }

    @Override
    public E set(int index, E element) {
        //获得index上的node
        Node<E> node = node(index);
        //保存原来的值
        E oldElement = node.element;
        //新值覆盖老值
        node.element = element;
        //返回老值
        return oldElement;
    }

    @Override
    public void add(int index, E element) {
        //当需要添加到末尾时
        if(index == size) {
            //拿到last节点
            Node l = last;
            //构建node 完成指向关系
            Node newNode = new Node(l,null,element);
            //将原来的last 节点的next 修改成新构建出来的node
            last = newNode;
            if(l == null){
                first = newNode;
            }else {
                l.next = newNode;
            }
        }else{
            //获得指定的index
            Node<E> node = node(index);
            //获得前一个结点
            Node<E> pre = node.pre;
            //构建新的now 完成指向关系
            Node<E> newNode = new Node(pre, node, element);
            //改变指向
            pre.next = newNode;
            if (pre == null) {
                first = newNode;
            } else {
                node.pre = newNode;
            }
        }
        size++;
    }

    //链表删除的主要原理就是将被删除者的前一个元素指向后一个元素
    //比如 A->B->C  当我要删除B的时候,就让A -> C
    @Override
    public E remove(int index) {
        //防止坐标越界
        if(index < 0 || index >= size){
            throw  new IndexOutOfBoundsException("index： " + index + " size: " + size);
        }
        //获得要删除的元素Node
        Node<E>node = node(index);
        //获得前一个结点
        Node<E> pre = node.pre;
        //获得后一个结点
        Node<E> next = node.next;

        if(pre == null){
            //firest进行修改
            first = next;
            next.pre = null;
        }else{
            //改变前一个结点的next
            pre.next = next;
        }
        
        if(next == null){
            //last进行修改
            last = pre;
        }else{
            next.pre = pre;
        }
        size--;
        //返回老元素
        return node.element;
    }

    @Override
    public int indexOf(E element) {
        //查找element元素是否存在,有返回索引,没有返回-1
        Node N = first;
        int index = 0;
        //遍历
        for(Node i = N; i != null; i = i.next){
            if(element == i.element){
                return index;
            }
            index++;
        }
        return -1;
    }

    @Override
    public void clear() {
        size = 0;
        first = null;
        last = null;
    }

    public String toString(){
        Node N = first;
        StringBuilder stringBuilder = new StringBuilder("[");
        boolean flag = false;   //判断是否循环到了最后
        for(Node i = N; i != null; i = i.next){
            //说明已经到了最后一个元素
            if(i.next == null) {
                flag = true;
            }
            //如果没到最后就加 逗号
            if(flag == false){
                stringBuilder.append(i.element + ",");
            }else{  //到了最后就不加逗号
                stringBuilder.append(i.element);
            }
        }
        stringBuilder.append("]");
        return stringBuilder.toString();
    }

    //内部Node节点类
    private static class Node<E>{
        Node<E> pre;
        Node<E> next;
        E element;
        public Node(Node next,E element){
            this.next = next;
            this.element = element;
        }

        public Node(Node pre,Node next,E element){
            this.pre = pre;
            this.next = next;
            this.element = element;
        }

        public Node() {

        }
    }
}

本文地址：https://blog.csdn.net/qq_41424688/article/details/112833156