Java基础之数组和链表

Bertha 。 2021-10-24 02:26 310阅读 0赞

数组的定义是：有限的相同类型的变量存储的集合。数组中的每一个变量称为元素，每一个元素都有自己的下标（从0开始）。数据在内存中是顺序存储。

数组的简单实现：

public class Array {
        
        //数据元素
        private int[] array;
        
        //当前数组存储数的个数
        private int size;
    
        public Array(int capacity){
            this.array = new int[capacity];
            this.size = 0;
        }
        /**
         * @Description
         * @Param  [num 添加的元素]
         * @Date 2019-8-18 20:31
         * @Version  1.0
         */
        public void add(int num){
            //对数组进行扩容
            if(size > array.length){
                resize();
            }
            //添加元素
            array[size++] = num;
        }
        /**
         * @Description 数组插入元素
         * @Param  [element 插入的数据, index 插入的位置]
         * @Date 2019-8-18 19:35
         * @Version  1.0
         */
        public void insert(int element,int index){
            //判断下表是否超出数组范围
            if(index < 0 || index > size){
                throw new IndexOutOfBoundsException("超出数组容量");
            }
            //对数组进行扩容
            if(size > array.length){
                resize();
            }
            for(int i = size - 1;i >= index;i--){
                array[i+1] = array[i];
            }
            //插入元素
            array[index] = element;
            size++;
        }
        /**
         * @Description 对数据进行扩容
         * @Param  null
         * @Date 2019-8-18 19:43
         * @Version  1.0
         */
        private void resize() {
            //数组扩容为原来的2倍
            int[] newArray = new int[array.length * 2];
            //将数据从旧的数组拷贝到新数组
            System.arraycopy(array,0,newArray,0,array.length);
            array = newArray;
        }
        /**
         * @Description 获取数据
         * @Param  [index 获取数据的下标]
         * @Date 2019-8-18 20:34
         * @Version  1.0
         */
        public int get(int index){
           return array[index];
        }
    
        public static void main(String[] args){
            Array array = new Array(10);
            array.insert(3,0);
            array.insert(2,1);
            array.insert(5,2);
            array.insert(6,3);
            array.insert(7,1);
            array.add(9);
            for (int i = 0; i < array.size; i++) {
                System.out.println(array.get(i));
            }
        }

需要注意的是数组有初始容量大小，当存储的元素达到最大容量时，是建立一个新的数组，容量为当前数组的2倍，然后将旧的数组的元素拷贝到新的数组。

链表的定义：在物理上非连续、非顺序存储的数结构，由节点组成。包含两部分，一个是存放的数据，另一个是指向下一节点的指针。链表的第一个节点称为头节点，最后一个为尾节点。

链表的简单实现：

public class Linked {
        //链表头节点
        private Node head;
        //链表未节点
        private Node last;
        //链表长度
        private int size;//默认值为0
    
        /**
         * @Description 链表末尾追加数据
         * @Param  [data 添加的数据]
         * @Date 2019-8-18 21:38
         * @Version  1.0
         */
        public void add(Object data) {
            Node inner = new Node(data);
            if(size == 0){
                head = inner;
                last = inner;
            }else{
               /* 没有理解对象引用
                Node node = get(size-1); //node==last
                node.next = inner;
                last = inner;*/
                //Node node = get(size-1);
                //System.out.println(node == last);//true
                last.next = inner;
                last = inner;
            }
            size++;
        }
        /**
         * @Description 链表插入元素
         * @Param  [data 插入的数据, index 插入的位置]
         * @Date 2019-8-18 21:01
         * @Version  1.0
         */
        public void insert(Object data,int index){
            if(index < 0 || index > size){
                throw new IndexOutOfBoundsException("下标越界");
            }
            Node inner = new Node(data);
            if(size == 0 ){//链表为空
                head = inner;
                last = inner;
            }else if(index == 0 ){//插入头部
                //System.out.println(head == last);//true 操作head相当于操作last
                inner.next = head;
                head = inner;
                //System.out.println(head.next == last);//true
                //System.out.println(inner.next == last);//true
            }else if(index == size){//尾部插入
                last.next = inner;
                last = inner;
            }else {//插入中间
                Node prevNode = get(index-1);
                if(prevNode == null){
                    throw new NullPointerException("下标链表为空！");
                }
                inner.next = prevNode.next;
                prevNode.next = inner;
            }
            size++;
        }
        /**
         * @Description
         * @Param  [index 删除的下标]
         * @Date 2019-8-18 21:28
         * @Version  1.0
         */
        public Node remove(int index) {
            if(index < 0 || index >= size){
                throw new IndexOutOfBoundsException("下标越界");
            }
            Node removeNode = null;
            if(index == 0){//删除头部
                removeNode = head;
                head = head.next;
            }else if(index == size){//删除尾部
                Node lastNode = get(index-1);
                removeNode = lastNode.next;
                lastNode.next = null;
                last = lastNode;
            }else{//删除中间
                Node pervNode = get(index-1);
                pervNode.next = pervNode.next.next;
                removeNode = pervNode.next;
            }
            return removeNode;
        }
        /**
         * @Description 根据下标获取链表节点
         * @Param  [index 下标]
         * @Date 2019-8-18 23:02
         * @Version  1.0
         */
        public Node get(int index) {
            if(index < 0 || index >= size){
                throw new IndexOutOfBoundsException("下标越界");
            }
            Node node = head;
            for (int i = 0; i < index; i++) {
                node = node.next;
                if(node.next == null){
                    break;
                }
            }
            return node;
        }
        /**
         * @Description 输出链表数据
         * @Param  NULL
         * @Date 2019-8-18 23:06
         * @Version  1.0
         */
        public void output(){
            Node next = head;
            while (next.next != null){
                System.out.println(next.data);
                next = next.next;
            }
            System.out.println(next.data);
        }
        /**
         * @Description 链表节点
         * @Date 2019-8-18 23:04
         * @Version  1.0
         */
        public static class Node {
            //存储的数据
            public Object data;
            //下一节点
            public Node next;
            public Node(Object data){
                this.data = data;
            }
        }
    
        public static void main(String[] args){
            Linked linked = new Linked();
            linked.add("123");
            linked.add(1234);
            linked.add("ad");
            linked.add("trt");
            linked.insert("111",0);
            linked.insert("222",2);
            linked.insert("333",6);
            linked.output();
            System.out.println("**************************");
            linked.remove(4);
            linked.output();
    
        }
    }

这里需要注意对象的存储和引用，对象是存储在堆上，栈只是拷贝一份对象的引用。就像链表中之存储了一个数据，头节点和尾节点都是指向这个数据存储的节点的，这时如果在头部插入一条数据，虽然操作的是头节点，但这时的头节点和尾节点是同一对象，相当于操作尾节点。

数据和链表的对比

*  数组的查找和更新快，只需操作一次，插入和删除操作N。
 *  链表查找慢，操作次数为N，更新、插入和删除只需一次。
 *  数组适用于读多写少，链表则相反。