数据结构第4讲数组、单链表和双链表-白红宇

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

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

链表是一系列的存储数据元素的单元通过指针串接起来形成的,因此链表的优点: 1.链表实现数据元素储存的顺序储存,是连续的 2.大小没有固定，拓展很灵活 3.不需要初始化容量，可以任意加减元素

链表的缺点: 1.不能随机查找，必须从第一个开始遍历，查找效率低 2.因为含有大量的指针域，占用空间较大

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

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

public class DoubleLink
    
      {    // 表头    private Head
     
       head;    // 节点个数    private int Count;    // 双向链表"节点"对应的结构体    private class Head
      
        {        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
       
        (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
        
          getNode(int index) {        if (index<0 || index>=Count)            throw new IndexOutOfBoundsException();        // 正向查找        if (index <= Count/2) {        	Head
         
           node = head.next; for (int i=0; i
          
            node = head.header; int rindex = Count - index -1; for (int j=0; j
           
             node = new Head
            
             (t, head, head.next); head.next.header = node; head.next = node; Count++; return ; } Head
             
               inode = getNode(index); Head
              
                tnode = new Head
               
                (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
                
                  node = new Head
                 
                  (t, head.header, head); head.header.next = node; head.header = node; Count++; } // 删除index位置的节点 public void del(int index) { Head
                  
                    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
    
      dlink = new DoubleLink
     
      ();        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 = new DoubleLink
       
        ();        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 = new DoubleLink
         
          (); 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