04、数据结构与算法-链表-笔记整理

链表的分类

链表分为:单链表,双向链表、单向循环链表
*

单链表
单链表添加实现思路
添加分为直接添加与指定位置添加
  • 直接添加尾节点next指针直接指向新元素即可
  • 指定位置添加需要一个辅助指针temp,如图
    *
    思路为:

1、 首先找到指定节点位置;
2、 新节点的next指针指向辅助指针temp的下一个节点:node.next=temp.next;
3、 辅助指针temp的下一个节点指向新节点:temp.next=node;

修改实现思路

找到临时指针temp直接修改里面的属性即可

删除思路

找到被删除节点的前一个节点,直接指向要删除节点的后一个节点即可
*

单链表代码实现
public class SingleLinkedListDemo {
   
     
    public static void main(String[] args) {
   
     
        Node node1 = new Node(1, "aaa");
        Node node2 = new Node(2, "bbb");
        Node node3 = new Node(3, "ccc");
        Node node4 = new Node(4, "ddd");
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.add(node1);
        singleLinkedList.add(node2);
        singleLinkedList.add(node3);
        singleLinkedList.add(node4);
        singleLinkedList.delete(4);
        Node node5 = new Node(3, "xxxx");
        singleLinkedList.update(node5);
        singleLinkedList.list();
    }
}
class SingleLinkedList {
   
     
    private Node head = new Node(0, "头结点");

    public Node getHead() {
   
     
        return head;
    }

    public void add(Node node) {
   
     
        Node temp = head;
        while (true) {
   
     
            if (temp.next == null) {
   
     
                break;
            }
            temp = temp.next;
        }
        temp.next = node;
    }

    public void add(int no, Node node) {
   
     
        Node temp = head;
        while (true) {
   
     
            if (temp.next == null) {
   
     //说明temp已经在链表的最后
                throw new RuntimeException("该节点不存在");
            }
            if (temp.no == no) {
   
     //找到了指定位置
                node.next = temp.next;
                temp.next = node;
                break;
            }
            temp = temp.next; //后移,遍历当前链表
        }
    }

    public void update(Node node) {
   
     
        if (head.next == null) {
   
     
            System.out.println("链表为空~");
            return;
        }
        Node temp = head.next;
        while (true) {
   
     
            if (temp == null) {
   
     
                System.out.println("更新失败,该节点不存在");
                break; //已经遍历完链表
            }
            if (temp.no == node.no) {
   
     
                //找到了要修改的节点
                temp.name = node.name;
                break;
            }
            temp = temp.next;
        }

    }

    public void delete(int no) {
   
     
        Node temp = head;
        while(true) {
   
     
            if(temp.next == null) {
   
     
                throw new RuntimeException("该节点不存在");
            }
            if(temp.next.no == no) {
   
     //找到的待删除节点的前一个节点temp
                temp.next = temp.next.next;
                break;
            }
            temp = temp.next; //temp后移,遍历
        }
    }

    public void list() {
   
     
        Node temp = head.next;
        while(true) {
   
     
            if(temp == null) {
   
     
                break;
            }
            System.out.println(temp);
            temp = temp.next;
        }
    }
    
    //反转链表
    public void reversalList(Node head) {
   
     
    if (head.next == null || head.next.next == null) {
   
     
        return;
    }
    Node cur = head.next;
    Node next;
    Node reverseHead = new Node(0, "头节点");
    while (cur != null) {
   
     
        next = cur.next;
        cur.next = reverseHead.next;
        reverseHead.next = cur;
        cur = next;
    }
    //将原来的链表指向新创建的反序列表
    head.next = reverseHead.next;
}

   //获取链表的长度
    public int getLength(Node head) {
   
     
        if (head.next == null) {
   
     
            return 0;
        }
        int length = 0;
        Node cur = head.next;
        while (cur != null) {
   
     
            length++;
            cur = cur.next;
        }
        return length;
    }

    //寻找链表的第index节点
    public Node getIndexNode(Node head, int index) {
   
     
        if (head.next == null) {
   
     
            return null;
        }
        int size = getLength(head);
        if (index <= 0 || index > size) {
   
     
            return null;
        }
        Node cur = head.next;
        for (int i = 0; i < size - index; i++) {
   
     
            cur = cur.next;
        }
        return cur;
    }

}

class Node {
   
     
    public int no;
    public String name;
    public Node next;

    public Node(int no, String name) {
   
     
        this.no = no;
        this.name = name;
    }

    @Override
    public String toString() {
   
     
       return "no="+no+",name="+name;
    }
}

双向链表
单链表与双向链表对比

1、 单链表查找只能是一个方向;
2、 单链表删除需要辅助节点,双向链表可以自我删除;
3、 双向链表可以向前也可以向后遍历;

双向链表实现思路

1、 遍历同单向链表;
2、 添加一个新节点相对比单链表需要维护两个指针:temp.next=node;node.pre=temp;;
*
3、 修改同单链表;
4、 删除指定节点思路:;
首先找到要删除的节点比如temp
公式为:temp.pre.next=temp.next;temp.next.pre=temp.pre
*

双向链表代码实现
 class DoubleLinkedList {
   
     
        private Node head = new Node(0, "头结点");
    
        public Node getHead() {
   
     
            return head;
        }
    
        public void add(Node node) {
   
     
            Node temp = head;
            while (true) {
   
     
                if (temp.next == null) {
   
     
                    break;
                }
                temp = temp.next;
            }
            temp.next = node;
            node.pre = temp;
        }
    
        public void update(Node node) {
   
     
            if (head.next == null) {
   
     
                System.out.println("链表为空~");
                return;
            }
            Node temp = head.next;
            while (true) {
   
     
                if (temp == null) {
   
     
                    System.out.println("更新失败,该节点不存在");
                    break; //已经遍历完链表
                }
                if (temp.no == node.no) {
   
     
                    //找到了要修改的节点
                    temp.name = node.name;
                    break;
                }
                temp = temp.next;
            }
    
        }
    
        public void delete(int no) {
   
     
            Node temp = head.next;
            if (temp == null) {
   
     
                throw new RuntimeException("这是个空链表");
            }
            while (true) {
   
     
                if (temp.no == no) {
   
     //找到的待删除节点
                    temp.pre.next = temp.next;
                    if (temp.next != null) {
   
     //如果是最后一个节点可能空指针
                        temp.next.pre = temp.pre;
                    }
                    break;
                }
                temp = temp.next; //temp后移,遍历
            }
        }
    
        public void list() {
   
     
            Node temp = head.next;
            while (true) {
   
     
                if (temp == null) {
   
     
                    break;
                }
                System.out.println(temp);
                temp = temp.next;
            }
        }
    
    }
    
    class Node {
   
     
        public int no;
        public String name;
        public Node next;
        public Node pre;
    
        Node(int no, String name) {
   
     
            this.no = no;
            this.name = name;
        }
    
        @Override
        public String toString() {
   
     
            return "no=" + no + ",name=" + name;
        }
    }

单向环形链表
使用单向环形列表解决约瑟夫环问题

*

实现思路

*

1、 构造一个first指针指向第一个节点、last指针指向最后一个节点;
2、 first与last指针移动k-1次,到编号为k的那个人位置;
3、 first与last移动m-1次,输出first所在的节点;
4、 删除first所在的节点,公式为:first=first.next;last.next=first;;
举例:
假如n=5,k=1,m=2依次输出为: 2->4->1->5->3

代码实现
public class Josepfu {
   
     

    public static void main(String[] args) {
   
     
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
        circleSingleLinkedList.addNode(5);// 加入5个节点
        circleSingleLinkedList.show();
        System.out.println("*************************************");
        circleSingleLinkedList.printNo(1, 2); // 2->4->1->5->3
    }

}

class CircleSingleLinkedList {
   
     
    private Node first = null;

    public void addNode(int nums) {
   
     
        if (nums < 1) {
   
     
            System.out.println("nums的值不正确");
            return;
        }
        Node cur = null; // 辅助指针,帮助构建环形链表
        for (int i = 1; i <= nums; i++) {
   
     
            Node node = new Node(i);
            // 如果是第一个节点
            if (i == 1) {
   
     
                first = node;
                first.next = first; // 构成环
                cur = first; // 让cur指向第一个节点
            } else {
   
     
                cur.next = node;
                node.next = first;
                cur = node;
            }
        }
    }

    public void show() {
   
     
        if (first == null) {
   
     
            System.out.println("没有任何数据");
            return;
        }
        Node cur = first;
        while (true) {
   
     
            System.out.printf("编号 %d \n", cur.no);
            if (cur.next == first) {
   
     // 说明已经遍历完毕
                break;
            }
            cur = cur.next;
        }
    }
    /**
     * k 表示从第k个开始数数
     * m 表示数几下
     */
    public void printNo(int k, int m) {
   
     
        if (first == null || k < 1) {
   
     
            System.out.println("参数输入有误, 请重新输入");
            return;
        }

        //创建一个last节点指向环形链表的最后一个节点位置
        Node last = first;
        while (true) {
   
     
            if (last.next == first) {
   
     
                break;
            }
            last = last.next;
        }

        //移动到第k个节点的位置
        for (int j = 0; j < k - 1; j++) {
   
     
            first = first.next;
            last = last.next;
        }

        while (true) {
   
     
            if (last == first) {
   
      //说明圈中只有一个节点
                break;
            }
            for (int j = 0; j < m - 1; j++) {
   
     
                first = first.next;
                last = last.next;
            }
            System.out.printf("节点%d出圈\n", first.no);
            //这时将first指向的节点出圈
            first = first.next;
            last.next = first;

        }
        System.out.printf("最后出圈的编号%d \n", first.no);

    }
}

class Node {
   
     
    public int no;// 编号
    public Node next; // 指向下一个节点,默认null

    Node(int no) {
   
     
        this.no = no;
    }

    @Override
    public String toString() {
   
     
        return "no=" + no;
    }

}

版权声明:本文不是「本站」原创文章,版权归原作者所有 | 原文地址: