双链表出现的背景

单链表结点中只有一个指向其后继的指针,使得单链表只能从头结点依次顺序地向后遍历。要访问某个结点的前驱结点(插入、删除操作时),只能从头开始遍历,访问后继结点的时间复杂度为O(1),访问前驱结点的时间复杂度为O(n)。

  • 单项链表,查找的方向只能是一个方向。
  • 单向链表不能自我删除,需要靠辅助结点,辅助节点为待删除结点的前一个结点。而双向链表可以自我删除。

双链表的增删改查

1.遍历同单链表一样,只是可以向前,也可以向后查找。
2.添加(默认添加到双向链表的最后)

  • 先找到双向链表的最后结点
  • tmp.next = new LinkNode;
  • new LinkNode.pre = tmp;

3.修改思路和原来单向链表一样
4.删除

  • 因为是双向链表,因此可以实现自我删除某个结点。
  • 直接找到要删除的结点。
  • tmp.pre.next = tmp.next
  • tmp.next.pre = tmp.pre
  • 注意如果是最后一个结点要进行判断,否则使用tmp.next.pre会出现空指针

双链表的代码实现

public class DoubleLinkedListDemo {
    public static void main(String[] args) {
        //测试
        System.out.println("双向链表测试");
        //创建结点
        LinkNode hero1 = new LinkNode(1, "宋江", "及时雨");
        LinkNode hero2 = new LinkNode(2, "卢俊义", "玉麒麟");
        LinkNode hero3 = new LinkNode(3, "吴用", "智多星");
        LinkNode hero4 = new LinkNode(4, "林冲", "豹子头");
        //创建一个双向列表:
        DoubleLinkedList dl = new DoubleLinkedList();

        dl.addNode(hero1);
        dl.addNode(hero2);
        dl.addNode(hero3);
        dl.addNode(hero4);
        dl.list();

        //修改一个结点:
        LinkNode newNode = new LinkNode(4, "公孙胜", "入云龙");
        dl.modify(newNode);

        System.out.println("修改后的链表的情况*********");
        dl.list();

        System.out.println("再次修改后的链表的情况*********");

        dl.delete(4);
        dl.list();

        System.out.println("再次再次修改后的链表的情况*********");

        dl.delete(1);
        dl.list();
    }
}

class DoubleLinkedList {
    // 初始化一个头结点
    LinkNode head = new LinkNode(0, "", "");

    // 返回头结点
    public LinkNode getHead() {
        return head;
    }

    // 读取链表
    public void list() {
        // 先判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        // 构造一个辅助指针,帮助遍历
        LinkNode tmp = head.next; // 此时指针在第一个结点处

        // 循环读取
        while (true) {
            if (tmp == null) {
                break;
            }

            //读取并输出结点信息
            System.out.println(tmp);

            //将tmp指针后移
            tmp = tmp.next;
        }
    }

    //修改链表结点
    public void modify(LinkNode newNode){
        //首先判断是否为空
        if(head.next==null){
            System.out.println("链表为空");
            return;
        }

        //找到需要修改的结点
        LinkNode tmp = head.next;
        boolean flag = false; //表示是否找到结点
        while(true){
            if(tmp==null){
                break; //到了链表末尾,仍未发现欲修改的结点
            }
            if(tmp.id == newNode.id){
                flag= true; //已经找到
                break;
            }
            tmp = tmp.next;
        }
        //根据flag判断是否找到要修改的结点
        if(flag){
            tmp.name = newNode.name;
            tmp.nickname = newNode.nickname;
        }else{
            System.out.println("没有找到要修改的结点!");
        }
    }

    //从双向列表中删除结点
    public void delete(int id){
        //先判断链表是否为空
        if(head.next == null){
            System.out.println("链表为空,无法删除");
            return;
        }
        //如果不为空,向后循环
        LinkNode tmp = head.next;
        boolean flag = false;
        while(true){
            if(tmp == null){ //已经找到链表末尾,仍未找到
                break;
            }
            if(tmp.id == id){
                //找到了待删除结点
                flag = true;
                break;
            }
            tmp = tmp.next;
        }
        if(flag){
            tmp.pre.next = tmp.next;

            //特别要警惕这一段代码:
            
            if(tmp.next != null){
                //如果是最后一个节点,就不需要执行下面的语句,否则会出现空指针异常。
                tmp.next.pre = tmp.pre;
            }
        }else{
            System.out.println("要删除的结点不存在");
        }

    }

    //添加结点的链表末尾
    public void addNode(LinkNode node){
        LinkNode tmp = head;
        while(true){
            if(tmp.next == null){
                break;
            }else{
                tmp = tmp.next;
            }
        }
        //当退出循环时,tmp指向链表的最后一个节点。
        tmp.next = node;
        node.pre = tmp;
    }
}

class LinkNode {
    public int id;
    public String name;
    public String nickname;
    public LinkNode pre;
    public LinkNode next;

    public LinkNode(int id, String name, String nickname) {
        this.id = id;
        this.name = name;
        this.nickname = nickname;
    }

    @Override
    public String toString() {
        return "Node [id=" + id + ", name=" + name + ", nickname=" + nickname + "]";
    }

}
Last modification:December 10th, 2020 at 01:33 am
如果觉得我的文章对你有用,请随意赞赏