侧边栏壁纸
博主头像
coydone博主等级

记录学习,分享生活的个人站点

  • 累计撰写 306 篇文章
  • 累计创建 51 个标签
  • 累计收到 0 条评论

目 录CONTENT

文章目录

链表

coydone
2021-06-04 / 0 评论 / 0 点赞 / 382 阅读 / 9,932 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

概述

使用顺序存储结构实现了线性表,我们会发现虽然顺序表的查询很快,时间复杂度为O(1),但是增删的效率是比较低的,因为每一次增删操作都伴随着大量的数据元素移动。这个问题有没有解决方案呢?有,我们可以使用另外一种存储结构实现线性表,链式存储结构。

链表(LinkedList)是一种物理存储单元上非连续、非顺序的存储结构,其物理结构不能直观的表示数据元素的逻辑顺序,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列的结点(链表中的每一个元素称为结点)组成,结点可以在运行时动态生成,是有序的列表。

链表是以节点的方式来存储,是链式存储,每个节点包含data域,next域(指向下一个节点),链表分为带头节点的链表和没有头节点的链表,根据实际的需求来确定。

按照面向对象的思想,我们可以设计一个类,来描述结点这个事物,用一个属性描述这个结点存储的元素,用另外一个属性描述这个结点的下一个结点。

类名 Node
构造方法 Node(T t,Node next):创建Node对象
成员变量 
	T item:存储数据
	Node next:指向下一个结点
public static class Node {
	public String item;
	public Node next;
	public Node(String item, Node next) {
		this.item = item;
		this.next = next;
	}
}

单向链表

单向链表是链表的一种,它由多个结点组成,每个结点都由一个数据域和一个指针域组成,数据域用来存储数据, 指针域用来指向其后继结点。链表的头结点的数据域不存储数据,指针域指向第一个真正存储数据的结点。

API设计

类名:LinkList
构造方法:LinkList():创建LinkList对象
成员方法:
	public void clear():空置线性表
	public boolean isEmpty():判断线性表是否为空,是返回true,否返回false
	public int length():获取线性表中元素的个数
	public E get(int i):读取并返回线性表中的第i个元素的值
	public void insert(E e):往线性表中添加一个元素;
	public void insert(int i,E e):在线性表的第i个元素之前插入值为e的数据元素
	public E remove(int i):删除并返回线性表中第i个数据元素。
	public int indexOf(E e):返回线性表中首次出现的指定的数据元素的位序号,若不存在,则返回-1。
成员内部类:private class Node:结点类
成员变量:
	private Node head:记录首结点
	private int n:记录链表的长度

代码实现

public class LinkList<E> {
    //记录首结点
    private Node<E> head;
    //记录链表的长度
    private int n;

    public LinkList() {
        // 初始化链表
        n = 0;
        head = new Node(null, null);
    }

    //空置线性表
    public void clear() {
        head.item = null;
        head.next = null;
        n = 0;

    }

    //判断线性表是否为空,是返回true,否返回false
    public boolean isEmpty() {
        return n == 0;
    }

    //获取线性表中元素的个数
    public int length() {
        return n;
    }

    //读取并返回线性表中的第index个元素的值
    public E get(int index) {
        if (index < 0 || index >= n) {
            throw new RuntimeException("下标不合法");
        }
        //获取第1个元素的结点
        Node<E> node = head.next;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node.item;
    }

    //往线性表中添加一个元素
    public void insert(E e) {
        // 找到最后一个节点
        Node node = head;
        // 只要node的下一个节点不为null,说明还有下一个元素
        while (node.next != null) {
            node = node.next;
        }
        // 到这里,node就是最后一个节点
        // 创建一个新的节点
        Node newNode = new Node(e, null);
        // 直接将最后一个节点的下一个结点指向新结点
        node.next = newNode;
        // 链表长度+1
        n++;
    }

    //在线性表的第i个元素之前插入值为e的数据元素
    public void insert(int index, E e) {
        if (index < 0 || index >= n) {
            throw new RuntimeException("位置不合法");
        }
        // 寻找index之前的节点
        // pre是我们要插入元素位置的上一个节点
        Node pre = head;
        for (int i = 0; i < index; i++) {
            // 取出下一个元素赋值给pre
            pre = pre.next;
        }
        // 到这里,插入下标的上一个节点就找到了
        // 取出index下一个位置的元素
        Node next = pre.next;
        // 构建新的Node
        Node newNode = new Node(e, next);
        pre.next = newNode;
        // 长度+1
        n++;
    }

    //删除并返回线性表中第index个数据元素
    public E remove(int index) {
        if(index < 0 || index >= n) {
            throw new RuntimeException("下标位置不合法");
        }
        // 寻找index之前的元素
        Node pre = head;
        for (int i = 0; i < index; i++) {
        // 取出下一个元素赋值给pre
            pre = pre.next;
        }
        // 到这里就找到了之前的元素
        // 获取当前index位置的结点
        Node<E> current = pre.next;
        // 获取当前index位置的下一个节点
        Node<E> next = current.next;
        // 前一个节点指向下一个节点
        pre.next = next;
        // 长度-1
        n--;
        return current.item;
    }

    //返回线性表中首次出现的指定的数据元素的位序号,若不存在返回-1
    public int indexOf(E e) {
        int index = 0;
        if (e == null) {
            for (LinkList.Node x = head; x != null; x = x.next) {
                if (x.item == null)
                    return index-1;
                index++;
            }
        } else {
            for (LinkList.Node x = head; x != null; x = x.next) {
                if (e.equals(x.item))
                    return index-1;
                index++;
            }
        }
        return -1;
    }
    
    private class Node<E> {
        public E item;
        public Node<E> next;
        public Node(E item, Node<E> next) {
            this.item = item;
            this.next = next;
        }
    }
}

双向链表

双向链表也叫双向表,是链表的一种,它由多个结点组成,每个结点都由一个数据域和两个指针域组成,数据域用来存储数据,其中一个指针域用来指向其后继结点,另一个指针域用来指向前驱结点。链表的头结点的数据域不存储数据,指向前驱结点的指针域值为null,指向后继结点的指针域指向第一个真正存储数据的结点。

节点API设计

类名:Node
构造方法:Node(T t,Node pre,Node next):创建Node对象
成员变量
T item:存储数据
Node next:指向下一个结点
Node pre:指向上一个结点

双向链表API设计

类名:TwoWayLinkList
构造方法:TwoWayLinkList():创建TowWayLinkList对象
成员方法
	public void clear():置空线性表
	public boolean isEmpty():判断线性表是否为空,是返回true,否返回false
	public int length():获取线性表中元素的个数
	public E get(int index):读取并返回线性表中的第index个元素的值
	public void insert(E e):往线性表中添加一个元素;
	public void insert(int i,E e):在线性表的第i个元素之前插入值为e的数据元素
	public E remove(int i):删除并返回线性表中第i个数据元素。
	public int indexOf(E e):返回线性表中首次出现的指定的数据元素的位序号,若不存在,则返回-1。
	public E getFirst():获取第一个元素
	public E getLast():获取最后一个元素
成员内部类:private class Node:结点类
成员变量
	private Node first:记录首结点
	private Node last:记录尾结点
	private int n:记录链表的长度

代码实现

//双向链表
public class TwoWayLinkList<E> {
    //记录首结点
    private Node<E> first;
    //记录尾结点
    private Node<E> last;
    //记录链表的长度
    private int n;

    public TwoWayLinkList() {
        first = new Node<>(null,null,null);
        last = null;
        n = 0;
    }

    //置空线性表
    public void clear(){
        last = null;
        first.pre = null;
        first.item = null;
        first.next = null;
        n = 0;
    }

    //判断线性表是否为空,是返回true,否返回false
    public boolean isEmpty(){
        return n == 0;
    }

    //获取线性表中元素的个数
    public int length() {
        return n;
    }

    //读取并返回线性表中的第index个元素的值
    public E get(int index){
        if (index < 0 || index >= n) {
            throw new RuntimeException("下标不合法");
        }
        //获取第1个元素的结点
        Node<E> node = first.next;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node.item;
    }

    //往线性表中添加一个元素
    public void insert(E e){
        if (last == null) {
            //如果last为空说明链表刚被初始化,那么第一个元素,就是last
            last = new Node<>(first,e,null);
            first.next = last;
        } else {
            // 说明链表已经有了元素
            Node<E> oldLast = this.last;
            Node<E> node = new Node<>(oldLast, e, null);
            oldLast.next = node;
            last = node;
        }
        //长度+1
        n++;

    }
    //在线性表的第index个元素之前插入值为e的数据元素
    public void insert(int index,E e){
        if (index < 0 || index >= n) {
            throw new RuntimeException("下标不合法");
        }
        // 获取头结点
        Node<E> pre = this.first;
        for (int i = 0; i < index; i++) {
            pre = pre.next;
        }
        // 到这里之后,我们就找到了待插入下标位置的前一个元素

        Node next = pre.next;
        //构建一个新的结点
        Node<E> newNode = new Node<>(pre, e, next);
        pre.next = newNode;
        next.pre = newNode;
        // 长度+1
        n++;
    }

    //删除并返回线性表中第index个数据元素
    public E remove(int index){
        if (index < 0 || index >= n) {
            throw new RuntimeException("下标不合法");
        }
        // 获取头结点
        Node pre = first;
        for (int i = 0; i < index; i++) {
            pre = pre.next;
        }
        // 到这里,pre就是我们要删除下标位置的前一个节点

        // 获取待删除的当前节点
        Node current = pre.next;
        // 获取待删除节点的下一个节点
        Node next = current.next;
        pre.next = next;
        next.pre = pre;
        // 长度-1
        n--;
        return (E) current.item;
    }

    //返回线性表中首次出现的指定的数据元素的位序号,若不存在返回-1
    public int indexOf(E e) {
        int index = 0;
        if (e == null) {
            for (Node x = first; x != null; x = x.next) {
                if (x.item == null)
                    return index-1;
                index++;
            }
        } else {
            for (Node x = first; x != null; x = x.next) {
                if (e.equals(x.item))
                    return index-1;
                index++;
            }
        }
        return -1;
    }

    //获取第一个元素
    public E getFirst() {
        if (isEmpty()) {
            return null;
        }
        return (E) first.next.item;

    }
    //获取最后一个元素
    public E getLast() {
        if (isEmpty()) {
            return null;
        }
        return last.item;
    }


    private class Node<E> {
        //存储数据
        E item;
        //指向上一个结点
        Node pre;
        //指向下一个结点
        Node next;
        Node(Node<E> pre, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.pre = pre;
        }
    }
}

时间复杂度

get(int i):每一次查询,都需要从链表的头部开始,依次向后查找,随着数据元素N的增多,比较的元素越多,时间复杂度为O(n);

insert(int i,E e):每一次插入,需要先找到i位置的前一个元素,然后完成插入操作,随着数据元素N的增多,查找的元素越多,时间复杂度为O(n);

remove(int i):每一次移除,需要先找到i位置的前一个元素,然后完成插入操作,随着数据元素N的增多,查找的元素越多,时间复杂度为O(n)。

相比较顺序表,链表插入和删除的时间复杂度虽然一样,但仍然有很大的优势,因为链表的物理地址是不连续的, 它不需要预先指定存储空间大小,或者在存储过程中涉及到扩容等操作,同时它并没有涉及的元素的交换。

相比较顺序表,链表的查询操作性能会比较低。因此,如果我们的程序中查询操作比较多,建议使用顺序表,增删操作比较多,建议使用链表。

结论:链表的查询性能比数组(顺序表)低,但是增删比数组高。其实,在我们使用的过程中,链表的使用频率是相当低的,因为只要我们尽可能的避免了顺序表的扩容,并且保证每次插入都是在顺序表最后一位插入,那么顺序表的增删操作性能也比链表要高。

单链表反转

需求:原链表中数据为:1→2→3→4;反转后链表中数据为:4→3→2→1。

思路:将head指针放在链表的最后面,然后改变链表的指针方向。

API设计:

public void reverse():对整个链表反转
private Node reverse(Node curr):反转链表中的某个结点curr,并把反转后的curr结点返回

使用递归可以完成反转,递归反转其实就是从原链表的第一个存数据的结点开始,依次递归调用反转每一个结点, 直到把最后一个结点反转完毕,整个链表就反转完毕。

代码实现:

//对整个链表反转
public void reverse() {
    //空链表,不反转
    if (n == 0) {
        return;
    }
    reverse(head.next);

}
//反转链表中的某个结点current,并把反转后的current结点返回
private Node<E> reverse(Node<E> current) {
    // 判断一下当前节点是否是最后一个节点
    if (current.next == null) {
    // 说明当前节点是最后一个节点
    // 最后一个节点需要让头节点指向它
        head.next = current;
        return current;
    }
    // 如果不是最后一个节点,反转下一个节点
    Node next = reverse(current.next);
    next.next = current;
    // 当前节点的下一个节点设为null
    current.next = null;
    return current;
}

循环链表

循环链表,顾名思义,链表整体要形成一个圆环状。在单向链表中,最后一个节点的指针为null,不指向任何结 点,因为没有下一个元素了。要实现循环链表,我们只需要让单向链表的最后一个节点的指针指向头结点即可。(循环链表中没有头指针)

//循环链表
public class LoopList {
    public static void main(String[] args) {
        Node n1 = new Node("1", null);
        Node n2 = new Node("2", null);
        Node n3 = new Node("3", null);
        Node n4 = new Node("4", null);
        // 构造循环链表
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n1;
    }

    private static class Node {
        public String item;
        public Node next;
        public Node(String item, Node next) {
            this.item = item;
            this.next = next;
        }
    }
}

约瑟夫环问题

问题描述:传说有这样一个故事,在罗马人占领乔塔帕特后,39 个犹太人与约瑟夫及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,第一个人从1开始报数,依次往后,如果有人报数到3,那么这个人就必须自杀,然后再由他的下一个人重新从1开始报数,直到所有人都自杀身亡为止。然而约瑟夫和他的朋友并不想遵从。于是,约瑟夫要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,从而逃过了这场死亡游戏 。

问题转换:

41个人坐一圈,第一个人编号为1,第二个人编号为2,第n个人编号为n。

1、编号为1的人开始从1报数,依次向后,报数为3的那个人退出圈;

2、自退出那个人开始的下一个人再次从1开始报数,以此类推;

3、求出最后退出的那个人的编号。

解题思路:

1.构建含有41个结点的单向循环链表,分别存储1~41的值,分别代表这41个人;
2.使用计数器count,记录当前报数的值;
3.遍历链表,每循环一次,count++;
4.判断count的值,如果是3,则从链表中删除这个结点并打印结点的值,把count重置为0;
//约瑟夫环问题
public class Joseph {
    public static void main(String[] args) {
        // 构建循环链表
        Node first = new Node(1, null);
        // 记录前一个节点
        Node pre = first;
        // 构造一个41节点的循环链表
        for (int i = 2; i <= 41; i++) {
            // 每一次循环,构建一个Node
            Node node = new Node(i, null);
            pre.next = node;
            // 记录当前节点为上一个节点
            pre = node;
            if (i == 41) {
                // 说明到最后了,让最后一个节点指向第一个节点
                pre.next = first;
            }
        }
        // 计数器count
        int count = 0;
        // 遍历链表,每次循环count++
        Node n = first;
        // 记录上一个节点
        Node back = null;
        // 循环链表
        while (n != n.next) {
            // 报数
            count++;
            // 判断count是否为3,如果是,删除当前节点
            if (count == 3) {
                back.next = n.next;
                System.out.println("当前死亡的人:" + n.item);
                // 计数器清零
                count = 0;
                // 下一个人继续
                n = n.next;
            } else {
                // 记录上一个节点
                back = n;
                // 下一个人继续
                n = n.next;
            }
        }
    }

    private static class Node {
        public int item;
        public Node next;

        public Node(int item, Node next) {
            this.item = item;
            this.next = next;
        }
    }
}

快慢指针

快慢指针指的是定义两个指针,这两个指针的移动速度一块一慢,以此来制造出自己想要的差值,这个差值可以让我们找到链表上相应的结点。一般情况下,快指针的移动步长为慢指针的两倍。

中间值问题

找出链表的中间元素值并返回。利用快慢指针,我们把一个链表看成一个跑道,假设a的速度是b的两倍,那么当a跑完全程后,b刚好跑一半,以此来达到找到中间节点的目的。

如下图,最开始,slow与fast指针都指向链表第一个节点,然后slow每次移动一个指针,fast每次移动两个指针。

private static int getMid(Node node) {
    // 给一个快指针
    Node fast = node;
    // 给一个慢指针
    Node slow = node;
    // 遍历链表,移动指针
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow.item;
}

单链表有环问题

单链表有环问题和循环链表是两码事。循环链表是我们为了解决某个问题而给出的解决方案。而单链表有环问题则是我们在使用链表的过程中失误操作锁带来的bug。

使用快慢指针的思想,还是把链表比作一条跑道,链表中有环,那么这条跑道就是一条圆环跑道,在一条圆环跑道中,两个人有速度差,那么迟早两个人会相遇,只要相遇那么就说明有环。

//判断当前链表是否有环
public static boolean isCircle(Node node) {
    Node slow = node;
    Node fast = node;
    // 遍历
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if(fast == slow) {
            return true;
        }
    }
    return false;
}

有环链表入口问题

查找有环链表中环的入口结点。当快慢指针相遇时,我们可以判断到链表中有环,这时重新设定一个新指针指向链表的起点,且步长与慢指针一样为1,则慢指针与“新”指针相遇的地方就是环的入口。

//获取有环链表的环入口,返回入口值
public static int getEnter(Node node) {
    Node slow = node;
    Node fast = node;
    // 定义一个新指针
    Node temp = null;
    // 遍历链表
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast == slow) {
            // 说明两个指针相遇了,有环,新指针开始移动
            temp = node;
            continue;
        }
        if (temp != null) {
            // temp不为空,说明新指针已经开始移动了
            temp = temp.next;
            // 判断一下新指针与慢指针是否相等,如相遇,则是环起点
            if (temp == slow) {
                return temp.item;
            }
        }
    }
    return 0;
}
0

评论区