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

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

image

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

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

image
image

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


image
image

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


image
image

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();    // 演示向双向链表操作"对象"。
    }
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 206,126评论 6赞 481
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 88,254评论 2赞 382
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 152,445评论 0赞 341
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 55,185评论 1赞 278
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 64,178评论 5赞 371
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,970评论 1赞 284
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,276评论 3赞 399
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,927评论 0赞 259
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 43,400评论 1赞 300
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,883评论 2赞 323
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,997评论 1赞 333
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,646评论 4赞 322
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,213评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,204评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,423评论 1赞 260
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 45,423评论 2赞 352
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,722评论 2赞 345