数据结构第4讲数组、单链表和双链表

- 日理万妓 2022-03-08 02:24 240阅读 0赞

数组：  
数组静态分配内存，在内存中连续  
存储0,10,20,30,40,的数组的示意图如下：

![image][]

数组的优点:  
1.使用方便,查询效率、  
2.随机访问性强（通过下标进行快速定位）  
数组的缺点:  
1.插入和删除效率低（插入和删除需要移动数据）  
2.可能浪费内存（因为是连续的，所以每次申请数组之前必须规定数组的大小，如果大小不合理，则可能会浪费内存）  
3.内存空间要求高，必须有足够的连续内存空间。  
4.数组大小固定，不能动态拓展

链表是一系列的存储数据元素的单元通过指针串接起来形成的,因此  
链表的优点:  
1.链表实现数据元素储存的顺序储存,是连续的  
2.大小没有固定，拓展很灵活  
3.不需要初始化容量，可以任意加减元素  
链表的缺点:  
1.不能随机查找，必须从第一个开始遍历，查找效率低  
2.因为含有大量的指针域，占用空间较大

![image][image 1]

![image][image 2]  
单链表：  
链表是动态分配内存在内存中不连续，单链表只有一个向下的指针，指向下一个节点，单链表的定位时间复杂度是O(n)，插入删除的时间复杂度是O(1)  
![image][image 3]

![image][image 4]  
双链表：  
链表是动态分配内容在内存中不连续，单双链表一致，双链表有两个指针header,next ，header指向上一个节点，next指向下一个节点  
![image][image 5]

![image][image 6]

public class DoubleLink<T> {
    
        // 表头
        private Head<T> head;
        // 节点个数
        private int Count;
    
        // 双向链表"节点"对应的结构体
        private class Head<T> {
            public Head header;
            public Head next;
            public T value;
    
            public Head(T value, Head header, Head next) {
                this.value = value;
                this.header =header;
                this.next = next;
            }
        }
    
        // 构造函数
        public DoubleLink() {
            // 创建"表头"。注意：表头没有存储数据！
            head = new Head<T>(null, null, null);
            head.header = head.next = head;
            // 初始化"节点个数"为0
            Count = 0;
        }
    
        // 返回节点数目
        public int size() {
            return Count;
        }
    
        // 返回链表是否为空
        public boolean isEmpty() {
            return Count==0;
        }
    
        // 获取第index位置的节点
        private Head<T> getNode(int index) {
            if (index<0 || index>=Count)
                throw new IndexOutOfBoundsException();
    
            // 正向查找
            if (index <= Count/2) {
            	Head<T> node = head.next;
                for (int i=0; i<index; i++)
                    node = node.next;
    
                return node;
            }
    
            // 反向查找
            Head<T> node = head.header;
            int rindex = Count - index -1;
            for (int j=0; j<rindex; j++)
                node = node.header;
    
            return node;
        }
    
        // 获取第index位置的节点的值
        public T get(int index) {
            return getNode(index).value;
        }
    
        // 获取第1个节点的值
        public T getFirst() {
            return getNode(0).value;
        }
    
        // 获取最后一个节点的值
        public T getLast() {
            return getNode(Count-1).value;
        }
    
        // 将节点插入到第index位置之前
        public void insert(int index, T t) {
            if (index==0) {
            	Head<T> node = new Head<T>(t, head, head.next);
                head.next.header = node;
                head.next = node;
                Count++;
                return ;
            }
    
            Head<T> inode = getNode(index);
            Head<T> tnode = new Head<T>(t, inode.header, inode);
            inode.header.next = tnode;
            inode.next = tnode;
            Count++;
            return ;
        }
    
        // 将节点插入第一个节点处。
        public void insertFirst(T t) {
            insert(0, t);
        }
    
        // 将节点追加到链表的末尾
        public void appendLast(T t) {
        	Head<T> node = new Head<T>(t, head.header, head);
        	head.header.next = node;
        	head.header = node;
            Count++;
        }
    
        // 删除index位置的节点
        public void del(int index) {
        	Head<T> inode = getNode(index);
            inode.header.next = inode.next;
            inode.next.header = inode.header;
            inode = null;
            Count--;
        }
    
        // 删除第一个节点
        public void deleteFirst() {
            del(0);
        }
    
        // 删除最后一个节点
        public void deleteLast() {
            del(Count-1);
        }
    }

public class DlinkTest {
    
        // 双向链表操作int数据
        private static void inttest() {
            int[] arr = {0,10,20,30};
    
            System.out.println("\n----inttest----");
            // 创建双向链表
            DoubleLink<Integer> dlink = new DoubleLink<Integer>();
    
            dlink.insert(0,10);    // 将 30 插入到第一个位置
            dlink.appendLast(20);    // 将 20 追加到链表末尾
            dlink.insertFirst(30);    // 将 40 插入到第一个位置
    
            // 双向链表是否为空
            System.out.printf("isEmpty()=%b\n", dlink.isEmpty());
            // 双向链表的大小
            System.out.printf("size()=%d\n", dlink.size());
    
            // 打印出全部的节点
            for (int i=0; i<dlink.size(); i++)
                System.out.println("dlink("+i+")="+ dlink.get(i));
        }
    
    
        private static void stringtest() {
            String[] array = {"zero","ten","twenty", "thirty"};
    
            System.out.println("\n----stringtest----");
            // 创建双向链表
            DoubleLink<String> dlink = new DoubleLink<String>();
    
            dlink.insert(0, array[1]);    // 将 array中第2个元素 插入到第一个位置
            dlink.appendLast(array[0]);    // 将 array中第1个元素 追加到链表末尾
            dlink.insertFirst(array[2]);    // 将 array中第3个元素 插入到第一个位置
    
            // 双向链表是否为空
            System.out.printf("isEmpty()=%b\n", dlink.isEmpty());
            // 双向链表的大小
            System.out.printf("size()=%d\n", dlink.size());
    
            // 打印出全部的节点
            for (int i=0; i<dlink.size(); i++)
                System.out.println("dlink("+i+")="+ dlink.get(i));
        }
    
    
        // 内部类
        private static class Student {
            private int id;
            private String name;
    
            public Student(int id, String name) {
                this.id = id;
                this.name = name;
            }
    
            @Override
            public String toString() {
                return "["+id+", "+name+"]";
            }
        }
    
        private static Student[] students = new Student[]{
            new Student(0, "xiaoming"),
            new Student(10, "xiaohua"),
            new Student(20, "xiaodan"),
            new Student(30, "xiaohong"),
        };
    
        private static void objecttest() {
            System.out.println("\n----objecttest----");
            // 创建双向链表
            DoubleLink<Student> dlink = new DoubleLink<Student>();
    
            dlink.insert(0, students[1]);    // 将 students中第2个元素 插入到第一个位置
            dlink.appendLast(students[0]);    // 将 students中第1个元素 追加到链表末尾
            dlink.insertFirst(students[2]);    // 将 students中第3个元素 插入到第一个位置
    
            // 双向链表是否为空
            System.out.printf("isEmpty()=%b\n", dlink.isEmpty());
            // 双向链表的大小
            System.out.printf("size()=%d\n", dlink.size());
    
            // 打印出全部的节点
            for (int i=0; i<dlink.size(); i++) {
                System.out.println("dlink("+i+")="+ dlink.get(i));
            }
        }
    
     
        public static void main(String[] args) {
            inttest();        // 演示向双向链表操作"int数据"。
            stringtest();    // 演示向双向链表操作"字符串数据"。
            objecttest();    // 演示向双向链表操作"对象"。
        }
    }

[image]: /images/20220308/eaea0df46bf745e1964ba3fad19829d1.png
[image 1]: /images/20220308/7975f5a6aa754d5cb7b9bf34ce404a1a.png
[image 2]: /images/20220308/3af7ffce37a04fa8be2db97d87ab1002.png
[image 3]: /images/20220308/bae3dc2c79b04c1eacaf81ad22ebe6c0.png
[image 4]: /images/20220308/914e0ae25ba74ef59413e34c9d26a6f3.png
[image 5]: /images/20220308/24e147c9f12f4bc08a58239723aff39f.png
[image 6]: /images/20220308/1586a6658a934c11833f19d02d0612ca.png