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

港控/mmm° 2023-01-08 08:09 104阅读 0赞

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

## [上一期][Link 1] ##

### 前言 ###

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

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

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

##### 存储方式比较 #####

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

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

### 相关博客 ###

[线性表的基本实现和概念][Link 2]

[顺序表的操作][Link 3]

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

## 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 ##

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

### 相关博客 ###

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

[单链表的增删查改][Link 5]

[双链表][Link 6]

[关于线性表的两个案例][Link 7]

### 单链表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() { 
    
            }
        }
    }

[Link 1]: https://blog.csdn.net/qq_41424688/article/details/112822960
[Link 2]: https://blog.csdn.net/qq_41424688/article/details/107329357
[Link 3]: https://blog.csdn.net/qq_41424688/article/details/107347257
[Link 4]: https://blog.csdn.net/qq_41424688/article/details/107354103
[Link 5]: https://blog.csdn.net/qq_41424688/article/details/107399270
[Link 6]: https://blog.csdn.net/qq_41424688/article/details/107471315
[Link 7]: https://blog.csdn.net/qq_41424688/article/details/107549602