链表

链表
强烈推介IDEA2020.2破解激活,IntelliJ IDEA 注册码,2020.2 IDEA 激活码

单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据。链表是有序的列表,但是它在内存中是存储如下:

一、单链表介绍


【1】一种最简单的结点结构如图所示,它是构成单链表的基本结点结构。在结点中数据域用来存储数据元素,指针域用于指向下一个具有相同结构的结点。因为只有一个指针结点,称为单链表:

【3】在单链表结构中还需要注意的一点是,由于每个结点的数据域都是一个 Object 类的对象,因此,每个数据元素并非真正如图中那样,而是在结点中的数据域通过一个 Object类的对象引用来指向数据元素的。与数组类似,单链表中的结点也具有一个线性次序,即如果结点 P 的 next 引用指向结点 S,则 P 就是 S 的直接前驱,S 是 P 的下一个节点。单链表的一个重要特性就是只能通过前驱结点找到下一个结点,而无法从后续结点找到前驱结点。

二、单链表的查询、添加、修改、删除操作


【1】查询操作:在单链表中进行查找操作,只能从链表的首结点开始,通过每个结点的 next 引用来一次访问链表中的每个结点以完成相应的查找操作。例如需要在单链表中查找是否包含某个数据元素 e,则方法是使用一个循环变量 p,起始时从单链表的头结点开始,每次循环判断 p所指结点的数据域是否和 e 相同,如果相同则可以返回 true,否则让p指向下一个节点,继续循环直到链表中所有结点均被访问,此时 p 为 null;后续代码会实现。
关键操作:① 起始条件:p = head;② 结束条件:找到(e.equals(p.getData())==true)未找到( p == null)③ p指向下一个结点:p  = p.getNext();
缺点:逐个比较,频繁移动指针,导致效率低下;

【2】修改操作:在单链表中修改数据,属于增删改查中最简单的操作,通过传入需要修改的节点对象,从链表的 head节点向下遍历,如果修改的节点编号NO等于链表中的某个编号NO则将链表中的节点修改为传入的节点即可。后续代码会实现。

【3】添加操作:在单链表中数据元素的插入,是通过在链表中插入数据元素所属的结点来完成的。对于链表的不同位置,插入的过程会有细微的差别。中间、末尾的添加过程其实是一样的,关键是在首部添加,会有不同,会改变整个单链表的起始结点。后续代码会实现。
关键操作:以添加中间结点为例:① 指明新结点的后继 s.setNext(p.getNext());或者 s.next = p.next;② 指明新结点的前驱(其实是指明前驱结点的后继是新结点) p.setNext(s);或者 p.next = s;
优缺点:添加节点不需要移动元素,只需要修改元素的指针即可,效率高。但是如果需要先查询到添加位置再添加新元素,因为有逐个查询的过程,效率不高。

【4】删除操作:类似添加操作,创建一个临时节点(temp)向下遍历,判断其 next节点是否等于需要删除的节点。如果等于则将临时的next节点指向 next节点的next节点。此时需要删除的节点就没有对象引用,JVM进行垃圾回收GC的时候则会回收此对象。后续代码会实现。

在使用单链表实现线性表的时候,为了使程序更加简洁,我们通常在单链表的最前面添加一个哑元结点,也称为头结点。在头结点中不存储任何实质的数据对象,其 next 域指向线性表中 0 号元素所在的结点,可以对空表、非空表的情况以及对首元结点进行统一处理,编程更方便,常用头结点。一个带头结点的单链表实现线性表的结构图如图所示:

三、单链表代码实例


package com.algorithms;

/**
 * 模拟单链表
 */
public class SingleLinkedList {
    //创建一个 head节点
    Node head = new Node(0,"");
    //向链表中添加元素,首先根据 no(模拟数组下标) 判断插入的位置
    public void insert(Node n) throws IllegalAccessException {
        //定义一个临时节点 插入、删除时使用
        Node temp = head;
        if(n == null || n.getNo() < 0){
            throw new IllegalAccessException("传入的参数不合法");
        }
        //先判断插入的节点,链表中是否存在
        Node node = get(n.getNo());
        if(node != null){
            System.out.println("该节点链表中已存在,不能插入");
            return;
        }
        //如果当前节点等于null 或者 小于 temp.next 的no说明插入在temp.next前面,temp的后面
        //因为是单链表,所以需要确定插入节点的前一个节点 temp 位置
        while(true){
            if(temp.getNext() ==null || n.getNo() < temp.getNext().getNo()){
                //第一步:现将temp的next复制给新的节点
                n.setNext(temp.getNext());
                //第二步:将temp的next 变量更改为新插入的节点
                temp.setNext(n);
                break;
            }else{
                temp = temp.getNext();
            }
        }
    }

    //向链表中查询元素
    public Node get(int index) throws IllegalAccessException {
        //定义一个临时节点 插入、删除时使用
        Node temp = head;
        if(index < 0){
            throw new IllegalAccessException("传入的参数不合法");
        }
        while(true){
            if(temp.getNext() == null){
                System.out.println("链表中不存在no="+index+"的元素");
                return null;
            }
            if(temp.getNext().getNo() == index){
                return temp.getNext();
            }else{
                temp = temp.getNext();
            }
        }
    }

    //修改节点  只能修改内容
    public void update(Node n) throws IllegalAccessException {
        //定义一个临时节点 插入、删除时使用
        Node temp = head;
        if(n == null){
          throw new IllegalAccessException("传入的参数不合法");
        }
        while (true){
            if(temp.getNext().getNo() == n.getNo()){
                System.out.println("修改元素成功");
                temp.getNext().setValue(n.getValue());
                break;
            }else{
                temp = temp.getNext();
            }
            if(temp.getNext() == null){
                System.out.println("链表中不存在的元素");
                break;
            }
        }
    }

    //删除节点,根据下标删除,根据节点的话其实也是获取下标相同的来删除
    public void remove(int index) throws IllegalAccessException {
        //定义一个临时节点 插入、删除时使用
        Node temp = head;
        if(index < 0){
            throw new IllegalAccessException("传入的参数不合法");
        }
        if(get(index) == null){
            System.out.println("删除的节点链表中不存在");
            return;
        }
        //判断temp的下一个节点是否等于当前节点
        while(true){
            if(temp.getNext().getNo() == index){
                //将Next 的指针移动到下一位
                temp.setNext(temp.getNext().getNext());
                break;
            }else{
                temp = temp.getNext();
            }
            if(temp.getNext() == null){
                System.out.println("删除的节点链表中不存在");
                break;
            }
        }
    }

    //查看链表中的信息
    public void list(){
        //定义一个临时节点 插入、删除时使用
        Node temp = head;
        while (temp.getNext() != null){
            System.out.println(temp.getNext().toString());
            temp = temp.getNext();
        }
    }
    //测试代码
    public static void main (String[] args) throws Exception {
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        Node first = new Node(1, "First");
        Node second = new Node(2, "Second");
        Node fourth = new Node(4, "Fourth");

        //添加
        singleLinkedList.insert(first);
        singleLinkedList.insert(second);
        singleLinkedList.insert(fourth);

        //展示
        singleLinkedList.list();

        //向链表中添加元素
        Node third = new Node(3, "Third");
        singleLinkedList.insert(third);
        //展示
        /*  如下,有序
            Node{no=1, value='First'}
            Node{no=2, value='Second'}
            Node{no=3, value='Third'}
            Node{no=4, value='Fourth'}
         */
        singleLinkedList.list();

        //插入相同元素
        //输出:该节点链表中已存在,不能插入
        singleLinkedList.insert(third);

        //修改节点
        third = new Node(3, "Third--update");
        singleLinkedList.update(third);
        //输出:Node{no=3, value='Third--update'}
        singleLinkedList.list();

        //删除节点
        singleLinkedList.remove(3);
        singleLinkedList.list();

        //获取 3 和 4
        Node node3 = singleLinkedList.get(3);
        Node node4 = singleLinkedList.get(4);
        /* 输出
            null
            Node{no=4, value='Fourth'}
         */
        System.out.println(node3);
        System.out.println(node4);

    }
}
class Node{
    //编号,排序的属性,唯一
    private int no;
    private String value;
    //单链表的特点,指向下一个与自己相同的对象
    private Node next;
    public Node(int no,String value){
        this.no=no;
        this.value = value;
    }

    public int getNo() {
        return no;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    public void setValue(String value) {
        this.value = value;
    }

    public String getValue() {
        return value;
    }

    @Override
    public String toString() {
        return "Node{" +
                "no=" + no +
                ", value='" + value + '\'' +
                '}';
    }
}

四、双向链表


单向链表的缺点:【1】单向链表,查找的方向只能是一个方向,而双向链表可以向前或者向后查找。
【2】单向链表不能自我删除,需要靠辅助节点 ,而双向链表,则可以自我删除,所以前面我们单链表删除时节点,总是找到temp,temp是待删除节点的前一 个节点;
与单向链表的区别:主要却别就是双向列表多了一个向前的指针 pre,能够通过当前节点,查看自己的上一个节点。方法的实现与单链表基本相同,就是由原来的只考虑 next 节点的情况,改变成了需要考虑 next 和 pre 两个节点而已;

本文来源程序猿进阶,由javajgs_com转载发布,观点不代表Java架构师必看的立场,转载请标明来源出处:https://javajgs.com/archives/8257

发表评论