【谈谈】链表的简述

太过爱你忘了你带给我的痛 2022-01-23 02:53 124阅读 0赞

说到数据存储结构，我们往往首先会想到数组，对表的操作我们也可由数组实现。虽然数组是由固定容量创建的，但在需要时可通过扩容创建一个不同的数组。通过这种方法解决为了使用数组需要对表的大小进行估计。

int []arr=new int[10];
    ...
    //扩容
    int []newArr=new int[arr.length*2];
    for(int i=0;pi<arr.length;i++){
        
    newArr[i]=arr[i];
    }
    arr=newArr;

在许多情形下的表是通过在高端进行插入操作建成的，其后只发生对数组的访问。在这种情况下，数组是表的一种恰当的实现。然而，如果是对表的一些插入和删除操作，特别是对表的前端进行，我们可能需要线性时间进行对表一半元素的操作，那数组就不是一个很好的选择了。这时候就需要另一种数据结构进行处理：链表。  
链表的概述：  
　链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。

使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。  
　　  
　　具体结构可参考下图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE2MjI2_size_16_color_FFFFFF_t_70]  
以下截图来自第三版《数据结构与算法分析 Java语言描述》![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE2MjI2_size_16_color_FFFFFF_t_70 1]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE2MjI2_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE2MjI2_size_16_color_FFFFFF_t_70 3]

具体操作实现代码如下：

package edu;
    
    public interface List {
        
        //填删改查
        public void add(Object o);
        public void remove(int index);
        public Object get(int index);
        public int size();
        public Iterator iterator();
    
    }

package edu;
    
    public interface Iterator {
        
        public boolean hasNext();
        public Object next();
    
    }

package edu.link;
    
    public class Node {
        
        Object data;
        Node next;
    }

package edu.link;
    
    import edu.Iterator;
    import edu.List;
    
    public class LinkedList implements List {
        
        Node head;
        int size = 0;
    
        public void add(Object data){
        
            Node temp  = new Node();
            temp.data = data;
            if(size == 0) {
        
                head = temp;
            }else {
        
                Node t = head;
                for (int i = 1; i < size; i++) {
        
                    t = t.next;
                }
                t.next = temp;
            }
            size++;
        }
    
    
    
        @Override
        public void remove(int index) {
        
    
        }
    
        public Object get(int index){
        
            if(index == 0) return head.data;
            if(index < 0 || index >= size) return null;
            Node t = head;
            for(int i = 1; i <= index ; i++){
        
                t = t.next;
            }
            return t.data;
        }
    
        @Override
        public int size() {
        
            return size;
        }
    
        @Override
        public Iterator iterator() {
        
            Iterator iter = new Iterator() {
        
                int i = 0;
                @Override
                public boolean hasNext() {
        
                    if(i < size) return true;
                    return false;
                }
                @Override
                public Object next() {
        
                    Object o = null;
                    if(i == 0) o = head.data;
                    else{
        
                        Node temp = head;
                        for(int t = 1 ; t <= i ; t++){
        
                            temp = temp.next;
                        }
                        o = temp.data;
                    }
                    i++;
                    return o;
                }
            };
            int i = 0;
            return iter;
        }
    }

package edu;
    
    
    import edu.link.LinkedList;
    
    class ArrayList implements List{
        
        private int length = 20;
        private Object[] data = new Object[length];
        private int size = 0;
    
        public Object get(int index){
        
            if(index < 0 || index >= size){
        
                return null;
            }
            return data[index];
        }
    
        @Override
        public int size() {
        
            return size;
        }
    
        @Override
        public Iterator iterator() {
        
    //        class ArrayIter implements Iterator{
        
    //
    //            @Override
    //            public boolean hasNext() {
        
    //                return false;
    //            }
    //
    //            @Override
    //            public Object next() {
        
    //                return null;
    //            }
    //        }
            Iterator iter = new Iterator(){
        
                private int i = 0;
                @Override
                public boolean hasNext() {
        
                    if(i < size) return true;
                    return false;
                }
    
                @Override
                public Object next() {
        
                    Object o = data[i];
                    i++;
                    return o;
                }
            };
            return iter;
        }
    
    
    
        public void remove(int i){
        
            if(i < 0 || i >= size){
        
                return;
            }
            if(i == size - 1) size--;//{20,30,44}   size:2
            for(int t = i ; t < size - 1 ;t++ ){
        
                data[t] = data[t + 1];
            }
            size--;
        }
    
        public void add(Object d){
        
            if(size < length) {
        
                this.data[size] = d;
            }else{
        
                length *= 2;
                Object[] b = new Object[length];
                for(int i = 0 ; i < size ; i++){
        
                    b[i] = data[i];
                }
                data = b;
                data[size] = d;
            }
            size++;
        }
    
    }
    
    public class 集合的概念 {
        
        public static void main(String[] args) {
        
            ArrayList bb = new ArrayList();
            bb.add(20);
            bb.add(222);
            bb.add(23);
    
    
            Iterator iter = bb.iterator();
            while(iter.hasNext()){
        
                System.out.println(iter.next());
            }
    
            List aa = new LinkedList();
            aa.add(20);
            aa.add(222);
            aa.add(23);
            Iterator it = aa.iterator();
            while(it.hasNext()){
        
                System.out.println(it.next());
            }
        }
    
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE2MjI2_size_16_color_FFFFFF_t_70]: /images/20220123/d92db0d5b842457d9c18d18df369ba00.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE2MjI2_size_16_color_FFFFFF_t_70 1]: /images/20220123/cdfb6226dce64647bfe76d2e8b3714c5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE2MjI2_size_16_color_FFFFFF_t_70 2]: /images/20220123/b74bff911f25428bb65547b2aaafbedc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE2MjI2_size_16_color_FFFFFF_t_70 3]: /images/20220123/1a4a40decd384b0ba3501e6977ad6850.png