精华内容
下载资源
问答
  • 线性结构链表

    千次阅读 多人点赞 2021-03-05 19:30:27
    目录第一章 单向链表介绍第二章 单向链表实现2.01、初始化链表结构2.02、判断链表是否为空2.03、获取当前链表长度2.04、连接链表两个结点2.05、释放链表结点指向2.06、返回链表最后结点2.07、返回链表首个结点2.08...

    目录


    项目地址:https://gitee.com/caochenlei/data-structures

    第一章 单向链表介绍

    链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针连接次序实现的。链表由一系列结点组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。

    单向链表(单链表)是链表的一种,其特点是链表的连接方向是单向的,对链表的访问要从头部开始顺序读取,head指针指向第一个结点又称为头结点,而终止于最后一个指向null的结点。链表的头结点的数据域不存储数据,而头结点的指针域指向第一个真正存储数据的结点。这里为了方便操作,我又增加了一个last结点,这个结点就是为了指向最后一个结点,节约操作时间,提升查询性能。

    第二章 单向链表实现

    2.01、定义链表的结点类

    /**
     * 单向链表实现代码
     */
    public class SinglyLinkedList<E> {
        //定义结点类
        public class Node {
            E data;     //代表结点数据
            Node next;  //指向下个结点
    
            public Node(E data) {
                this.data = data;
            }
    
            @Override
            public String toString() {
                return "Node{data=" + data + "}";
            }
        }
    
        //下节内容写这...
    }
    

    2.02、定义链表的属性值

    /**
     * 单向链表实现代码
     */
    public class SinglyLinkedList<E> {
        //省略以上代码...
    
        private Node head;  //代表链表头部
        private Node last;  //代表链表尾部
        private int size;   //代表链表长度
    
        //下节内容写这...
    }
    

    2.03、初始化各个属性值

    /**
     * 单向链表实现代码
     */
    public class SinglyLinkedList<E> {
        //省略以上代码...
    
        public SinglyLinkedList() {
            //头结点用于其他结点的连接,头结点的下标我们定义为-1
            this.head = new Node(null);
            //尾结点初始默认指向头结点,这样我们在添加的时候方便
            this.last = head;
            this.size = 0;
        }
    
        //下节内容写这...
    }
    

    2.04、获取链表当前大小

    //获取链表当前大小
    public int size() {
        return size;
    }
    

    2.05、判断链表是否为空

    //判断链表是否为空
    public boolean isEmpty() {
        return size == 0;
    }
    

    2.06、检查下标是否合法

    //检查下标是否合法
    public void checkIndex(int index) {
        if (index < 0 || (size - 1) < index) {
            throw new IndexOutOfBoundsException("链表下标越界异常,请检查链表的下标!");
        }
    }
    

    2.07、连接链表两个结点

    //连接链表两个结点
    public void connectNode(Node prevNode, Node nextNode) {
        if (prevNode != null) {
            prevNode.next = nextNode;
        }
    }
    

    2.08、释放链表指定结点

    //释放链表指定结点
    public void releaseNode(Node node) {
        if (node != null) {
            node.data = null;
            node.next = null;
        }
    }
    

    2.09、返回链表最后结点

    //返回链表最后结点
    public Node getLast() {
        //判断链表是否为空
        if (isEmpty()) {
            return null;
        }
        //返回链表最后结点
        return last;
    }
    

    2.10、返回链表首个结点

    //返回链表首个结点
    public Node getFirst() {
        //判断链表是否为空
        if (isEmpty()) {
            return null;
        }
        //返回链表首个结点
        return head.next;
    }
    

    2.11、获取指定位置结点

    //获取指定位置结点
    public Node getIndex(int index) {
        //检查下标是否合法
        checkIndex(index);
        //获取指定位置结点
        Node curNode = head;
        for (int i = 0; i < (index + 1); i++) {
            curNode = curNode.next;
        }
        //返回指定位置结点
        return curNode;
    }
    

    2.12、获取位置之前结点

    //获取位置之前结点
    private Node getIndexPre(int index) {
        //检查下标是否合法
        checkIndex(index);
        //获取位置之前结点
        Node preNode = head;
        for (int i = 0; i < index; i++) {
            preNode = preNode.next;
        }
        //返回位置之前结点
        return preNode;
    }
    

    2.13、链表尾后添加数据

    默认为空的时候,头指针head和尾指针last均指向头结点。

    添加数据的时候,我们直接向last指向结点后追加结点即可。


    方法实现:

    //链表尾后添加数据(需要考虑last指向问题)
    public void addLast(E e) {
        //获取旧的尾结点
        Node oldLast = last;
        //创建新的尾结点
        Node newLast = new Node(e);
        //旧新两结点连接
        connectNode(oldLast, newLast);
        //修改last指向
        last = newLast;
        //使链表长度加一
        size++;
    }
    

    方法测试:

    public class SinglyLinkedListTest {
        public static void main(String[] args) {
            SinglyLinkedList<String> linkedList = new SinglyLinkedList<>();
    
            linkedList.addLast("张三");
            linkedList.addLast("李四");
            linkedList.addLast("王五");
    
            System.out.println("==========打印链表基本信息:");
            System.out.println("链表结点个数:" + linkedList.size());
            System.out.println("链表是否为空:" + linkedList.isEmpty());
            System.out.println("==========打印链表所有结点:");
            for (int i = 0; i < linkedList.size(); i++) {
                System.out.println(linkedList.getIndex(i));
            }
            System.out.println("==========打印链表首尾结点:");
            System.out.println("链表的头结点:" + linkedList.getFirst());
            System.out.println("链表的尾结点:" + linkedList.getLast());
        }
    }
    

    运行结果:

    ==========打印链表基本信息:
    链表结点个数:3
    链表是否为空:false
    ==========打印链表所有结点:
    Node{data=张三}
    Node{data=李四}
    Node{data=王五}
    ==========打印链表首尾结点:
    链表的头结点:Node{data=张三}
    链表的尾结点:Node{data=王五}
    

    2.14、链表头后添加数据

    方法实现:

    //链表头后添加数据(不用考虑last指向问题)
    public void addFirst(E e) {
        //判断链表是否为空
        if (isEmpty()) {
            addLast(e);
        } else {
            //获取首个结点
            Node firNode = head.next;
            //创建新的结点
            Node newNode = new Node(e);
            //三个结点连接
            connectNode(head, newNode);
            connectNode(newNode, firNode);
            //链表长度加一
            size++;
        }
    }
    

    方法测试:

    public class SinglyLinkedListTest {
        public static void main(String[] args) {
            SinglyLinkedList<String> linkedList = new SinglyLinkedList<>();
    
            linkedList.addFirst("张三");
            linkedList.addFirst("李四");
            linkedList.addFirst("王五");
    
            System.out.println("==========打印链表基本信息:");
            System.out.println("链表结点个数:" + linkedList.size());
            System.out.println("链表是否为空:" + linkedList.isEmpty());
            System.out.println("==========打印链表所有结点:");
            for (int i = 0; i < linkedList.size(); i++) {
                System.out.println(linkedList.getIndex(i));
            }
            System.out.println("==========打印链表首尾结点:");
            System.out.println("链表的头结点:" + linkedList.getFirst());
            System.out.println("链表的尾结点:" + linkedList.getLast());
        }
    }
    

    运行结果:

    ==========打印链表基本信息:
    链表结点个数:3
    链表是否为空:false
    ==========打印链表所有结点:
    Node{data=王五}
    Node{data=李四}
    Node{data=张三}
    ==========打印链表首尾结点:
    链表的头结点:Node{data=王五}
    链表的尾结点:Node{data=张三}
    

    2.15、指定位置添加数据

    方法实现:

    //指定位置添加数据(不用考虑last指向问题)
    public void addIndex(int index, E e) {
        //获取位置之前结点
        Node preNode = getIndexPre(index);
        //获取指定位置结点
        Node curNode = preNode.next;
        //创建一个新的结点
        Node newNode = new Node(e);
        //开始三个结点连接
        connectNode(preNode, newNode);
        connectNode(newNode, curNode);
        //当前链表长度加一
        size++;
    }
    

    方法测试:

    public class SinglyLinkedListTest {
        public static void main(String[] args) {
            SinglyLinkedList<String> linkedList = new SinglyLinkedList<>();
    
            linkedList.addLast("张三");
            linkedList.addLast("李四");
            linkedList.addLast("王五");
    
            linkedList.addIndex(0, "张三长辈");
            linkedList.addIndex(linkedList.size() - 1, "王五长辈");
    
            System.out.println("==========打印链表基本信息:");
            System.out.println("链表结点个数:" + linkedList.size());
            System.out.println("链表是否为空:" + linkedList.isEmpty());
            System.out.println("==========打印链表所有结点:");
            for (int i = 0; i < linkedList.size(); i++) {
                System.out.println(linkedList.getIndex(i));
            }
            System.out.println("==========打印链表首尾结点:");
            System.out.println("链表的头结点:" + linkedList.getFirst());
            System.out.println("链表的尾结点:" + linkedList.getLast());
        }
    }
    

    运行结果:

    ==========打印链表基本信息:
    链表结点个数:5
    链表是否为空:false
    ==========打印链表所有结点:
    Node{data=张三长辈}
    Node{data=张三}
    Node{data=李四}
    Node{data=王五长辈}
    Node{data=王五}
    ==========打印链表首尾结点:
    链表的头结点:Node{data=张三长辈}
    链表的尾结点:Node{data=王五}
    

    2.16、删除指定位置结点

    方法实现:

    //删除指定位置结点(需要考虑last指向问题)
    public void removeIndex(int index) {
        //获取位置之前结点
        Node preNode = getIndexPre(index);
        //获取指定位置结点
        Node curNode = preNode.next;
        //获取位置之后结点
        Node nexNode = curNode.next;
        //修改last的指向
        if (curNode == last) {
            last = preNode;
        }
        //删除指定位置结点
        connectNode(preNode, nexNode);
        //释放链表指定结点
        releaseNode(curNode);
        //当前链表长度减一
        size--;
    }
    

    方法测试:

    public class SinglyLinkedListTest {
        public static void main(String[] args) {
            SinglyLinkedList<String> linkedList = new SinglyLinkedList<>();
    
            linkedList.addLast("张三");
            linkedList.addLast("李四");
            linkedList.addLast("王五");
    
            linkedList.removeIndex(0);
            linkedList.removeIndex(linkedList.size() - 1);
    
            System.out.println("==========打印链表基本信息:");
            System.out.println("链表结点个数:" + linkedList.size());
            System.out.println("链表是否为空:" + linkedList.isEmpty());
            System.out.println("==========打印链表所有结点:");
            for (int i = 0; i < linkedList.size(); i++) {
                System.out.println(linkedList.getIndex(i));
            }
            System.out.println("==========打印链表首尾结点:");
            System.out.println("链表的头结点:" + linkedList.getFirst());
            System.out.println("链表的尾结点:" + linkedList.getLast());
        }
    }
    

    运行结果:

    ==========打印链表基本信息:
    链表结点个数:1
    链表是否为空:false
    ==========打印链表所有结点:
    Node{data=李四}
    ==========打印链表首尾结点:
    链表的头结点:Node{data=李四}
    链表的尾结点:Node{data=李四}
    

    2.17、删除链表首个结点

    方法实现:

    //删除链表首个结点(不用考虑last指向问题)
    public void removeFirst() {
        //判断链表是否为空
        if (isEmpty()) {
            return;
        }
        //删除链表首个结点
        removeIndex(0);
    }
    

    方法测试:

    public class SinglyLinkedListTest {
        public static void main(String[] args) {
            SinglyLinkedList<String> linkedList = new SinglyLinkedList<>();
    
            linkedList.addLast("张三");
            linkedList.addLast("李四");
            linkedList.addLast("王五");
    
            linkedList.removeFirst();
    
            System.out.println("==========打印链表基本信息:");
            System.out.println("链表结点个数:" + linkedList.size());
            System.out.println("链表是否为空:" + linkedList.isEmpty());
            System.out.println("==========打印链表所有结点:");
            for (int i = 0; i < linkedList.size(); i++) {
                System.out.println(linkedList.getIndex(i));
            }
            System.out.println("==========打印链表首尾结点:");
            System.out.println("链表的头结点:" + linkedList.getFirst());
            System.out.println("链表的尾结点:" + linkedList.getLast());
        }
    }
    

    运行结果:

    ==========打印链表基本信息:
    链表结点个数:2
    链表是否为空:false
    ==========打印链表所有结点:
    Node{data=李四}
    Node{data=王五}
    ==========打印链表首尾结点:
    链表的头结点:Node{data=李四}
    链表的尾结点:Node{data=王五}
    

    2.18、删除链表最后结点

    方法实现:

    //删除链表最后结点(不用考虑last指向问题)
    public void removeLast() {
        //判断链表是否为空
        if (isEmpty()) {
            return;
        }
        //删除链表最后结点
        removeIndex(size - 1);
    }
    

    方法测试:

    public class SinglyLinkedListTest {
        public static void main(String[] args) {
            SinglyLinkedList<String> linkedList = new SinglyLinkedList<>();
    
            linkedList.addLast("张三");
            linkedList.addLast("李四");
            linkedList.addLast("王五");
    
            linkedList.removeLast();
    
            System.out.println("==========打印链表基本信息:");
            System.out.println("链表结点个数:" + linkedList.size());
            System.out.println("链表是否为空:" + linkedList.isEmpty());
            System.out.println("==========打印链表所有结点:");
            for (int i = 0; i < linkedList.size(); i++) {
                System.out.println(linkedList.getIndex(i));
            }
            System.out.println("==========打印链表首尾结点:");
            System.out.println("链表的头结点:" + linkedList.getFirst());
            System.out.println("链表的尾结点:" + linkedList.getLast());
        }
    }
    

    运行结果:

    ==========打印链表基本信息:
    链表结点个数:2
    链表是否为空:false
    ==========打印链表所有结点:
    Node{data=张三}
    Node{data=李四}
    ==========打印链表首尾结点:
    链表的头结点:Node{data=张三}
    链表的尾结点:Node{data=李四}
    

    2.19、输出链表所有结点

    方法实现:

    //输出链表所有结点(不用考虑last指向问题)
    public void show() {
        //判断链表是否为空
        if (isEmpty()) {
            return;
        }
        //遍历链表所有结点(除头结点)
        Node curNode = head.next;
        while (curNode != null) {
            System.out.println(curNode);
            curNode = curNode.next;
        }
    }
    

    方法测试:

    public class SinglyLinkedListTest {
        public static void main(String[] args) {
            SinglyLinkedList<String> linkedList = new SinglyLinkedList<>();
    
            linkedList.addLast("张三");
            linkedList.addLast("李四");
            linkedList.addLast("王五");
    
            System.out.println("==========打印链表基本信息:");
            System.out.println("链表结点个数:" + linkedList.size());
            System.out.println("链表是否为空:" + linkedList.isEmpty());
            System.out.println("==========打印链表所有结点:");
            linkedList.show();
            System.out.println("==========打印链表首尾结点:");
            System.out.println("链表的头结点:" + linkedList.getFirst());
            System.out.println("链表的尾结点:" + linkedList.getLast());
        }
    }
    

    运行结果:

    ==========打印链表基本信息:
    链表结点个数:3
    链表是否为空:false
    ==========打印链表所有结点:
    Node{data=张三}
    Node{data=李四}
    Node{data=王五}
    ==========打印链表首尾结点:
    链表的头结点:Node{data=张三}
    链表的尾结点:Node{data=王五}
    

    2.20、反转链表所有结点

    方法实现:

    //反转链表所有结点(需要考虑last指向问题)
    public void reverse() {
        //判断链表是否为空
        if (isEmpty()) {
            return;
        }
        //创建一个新头结点
        Node newHead = new Node(null);
        //获取链表的首结点
        Node oldFirst = head.next;
        //遍历链表所有结点(除头结点)
        Node newFirst;
        Node tmpNode;
        Node curNode = oldFirst;
        while (curNode != null) {
            //缓存当前结点下个结点
            tmpNode = curNode.next;
            //获取链表新头首个结点
            newFirst = newHead.next;
            //开始三个结点进行关联
            connectNode(newHead, curNode);
            connectNode(curNode, newFirst);
            //让当前的结点往后移动
            curNode = tmpNode;
        }
        //老头换新头首结点
        head.next = newHead.next;
        //修改last的指向
        last = oldFirst;
        //释放临时新头结点
        releaseNode(newHead);
    }
    

    方法测试:

    public class SinglyLinkedListTest {
        public static void main(String[] args) {
            SinglyLinkedList<String> linkedList = new SinglyLinkedList<>();
    
            linkedList.addLast("张三");
            linkedList.addLast("李四");
            linkedList.addLast("王五");
    
            linkedList.reverse();
    
            System.out.println("==========打印链表基本信息:");
            System.out.println("链表结点个数:" + linkedList.size());
            System.out.println("链表是否为空:" + linkedList.isEmpty());
            System.out.println("==========打印链表所有结点:");
            linkedList.show();
            System.out.println("==========打印链表首尾结点:");
            System.out.println("链表的头结点:" + linkedList.getFirst());
            System.out.println("链表的尾结点:" + linkedList.getLast());
        }
    }
    

    运行结果:

    ==========打印链表基本信息:
    链表结点个数:3
    链表是否为空:false
    ==========打印链表所有结点:
    Node{data=王五}
    Node{data=李四}
    Node{data=张三}
    ==========打印链表首尾结点:
    链表的头结点:Node{data=王五}
    链表的尾结点:Node{data=张三}
    

    2.21、清空链表所有结点

    方法实现:

    //清空链表所有结点(需要考虑last指向问题)
    public void clear() {
        //判断链表是否为空
        if (isEmpty()) {
            return;
        }
        //遍历链表所有结点(含头结点)
        Node tmpNode;
        Node curNode = head;
        while (curNode != null) {
            //缓存下个结点
            tmpNode = curNode.next;
            //释放当前结点
            releaseNode(curNode);
            //移动下个结点
            curNode = tmpNode;
        }
        //重置链表基本信息
        head = null;
        last = null;
        size = 0;
    }
    

    方法测试:

    public class SinglyLinkedListTest {
        public static void main(String[] args) {
            SinglyLinkedList<String> linkedList = new SinglyLinkedList<>();
    
            linkedList.addLast("张三");
            linkedList.addLast("李四");
            linkedList.addLast("王五");
    
            linkedList.clear();
    
            System.out.println("==========打印链表基本信息:");
            System.out.println("链表结点个数:" + linkedList.size());
            System.out.println("链表是否为空:" + linkedList.isEmpty());
            System.out.println("==========打印链表所有结点:");
            linkedList.show();
            System.out.println("==========打印链表首尾结点:");
            System.out.println("链表的头结点:" + linkedList.getFirst());
            System.out.println("链表的尾结点:" + linkedList.getLast());
        }
    }
    

    运行结果:

    ==========打印链表基本信息:
    链表结点个数:0
    链表是否为空:true
    ==========打印链表所有结点:
    ==========打印链表首尾结点:
    链表的头结点:null
    链表的尾结点:null
    

    2.22、顺序查找数据首次出现位置

    方法实现:

    //顺序查找数据首次出现位置
    public int indexOf(E e) {
        //判断链表是否为空
        if (isEmpty()) {
            return -1;
        }
        //判断对象是否为空
        if (e == null) {
            return -1;
        }
        //获取指定位置结点
        Node curNode = head;
        for (int i = -1; i < size; i++) {
            if (e.equals(curNode.data)) {
                return i;
            }
            curNode = curNode.next;
        }
        //没有找到返回负一
        return -1;
    }
    

    方法测试:

    public class SinglyLinkedListTest {
        public static void main(String[] args) {
            SinglyLinkedList<String> linkedList = new SinglyLinkedList<>();
    
            linkedList.addLast("张三");
            linkedList.addLast("李四");
            linkedList.addLast("王五");
    
            System.out.println(linkedList.indexOf("张三"));
            System.out.println(linkedList.indexOf("李四"));
            System.out.println(linkedList.indexOf("王五"));
    
            System.out.println("==========打印链表基本信息:");
            System.out.println("链表结点个数:" + linkedList.size());
            System.out.println("链表是否为空:" + linkedList.isEmpty());
            System.out.println("==========打印链表所有结点:");
            linkedList.show();
            System.out.println("==========打印链表首尾结点:");
            System.out.println("链表的头结点:" + linkedList.getFirst());
            System.out.println("链表的尾结点:" + linkedList.getLast());
        }
    }
    

    运行结果:

    0
    1
    2
    ==========打印链表基本信息:
    链表结点个数:3
    链表是否为空:false
    ==========打印链表所有结点:
    Node{data=张三}
    Node{data=李四}
    Node{data=王五}
    ==========打印链表首尾结点:
    链表的头结点:Node{data=张三}
    链表的尾结点:Node{data=王五}
    

    2.23、逆序查找数据首次出现位置

    方法实现:

    //逆序查找数据首次出现位置
    public int lastIndexOf(E e) {
        //判断链表是否为空
        if (isEmpty()) {
            return -1;
        }
        //判断对象是否为空
        if (e == null) {
            return -1;
        }
        //反转当前链表结点
        reverse();
        //获取指定位置结点
        int index = indexOf(e);
        //反转当前链表结点
        reverse();
        //返回数据指定位置
        return index;
    }
    

    方法测试:

    public class SinglyLinkedListTest {
        public static void main(String[] args) {
            SinglyLinkedList<String> linkedList = new SinglyLinkedList<>();
    
            linkedList.addLast("张三");
            linkedList.addLast("李四");
            linkedList.addLast("王五");
    
            System.out.println(linkedList.lastIndexOf("张三"));
            System.out.println(linkedList.lastIndexOf("李四"));
            System.out.println(linkedList.lastIndexOf("王五"));
    
            System.out.println("==========打印链表基本信息:");
            System.out.println("链表结点个数:" + linkedList.size());
            System.out.println("链表是否为空:" + linkedList.isEmpty());
            System.out.println("==========打印链表所有结点:");
            linkedList.show();
            System.out.println("==========打印链表首尾结点:");
            System.out.println("链表的头结点:" + linkedList.getFirst());
            System.out.println("链表的尾结点:" + linkedList.getLast());
        }
    }
    

    运行结果:

    2
    1
    0
    ==========打印链表基本信息:
    链表结点个数:3
    链表是否为空:false
    ==========打印链表所有结点:
    Node{data=张三}
    Node{data=李四}
    Node{data=王五}
    ==========打印链表首尾结点:
    链表的头结点:Node{data=张三}
    链表的尾结点:Node{data=王五}
    

    第三章 双向链表介绍

    双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。链表的头结点的数据域不存储数据,指向前驱结点的指针域值为null,指向后继结点的指针域指向第一个真正存储数据结点。

    第四章 双向链表实现

    4.01、且看代码如此多娇

    我们已经学过了单向链表的设计和实现了,双向链表只需要在单向链表的基础上添加三行代码就能实现,你看神奇不神奇。

    我们需要直接拷贝SinglyLinkedListDoublyLinkedList,然后拷贝SinglyLinkedListTestDoublyLinkedListTest,并修改相对应的构造方法名称。

    第一处:修改节点类,添加prev指针域。

    //定义结点类
    public class Node {
        Node prev;  //指向上个结点 +
        E data;     //代表结点数据
        Node next;  //指向下个结点
    
        public Node(E data) {
            this.data = data;
        }
    
        @Override
        public String toString() {
            return "Node{data=" + data + "}";
        }
    }
    

    第二处:修改连接处,添加指向上个结点。

    //连接链表两个结点
    public void connectNode(Node prevNode, Node nextNode) {
        if (prevNode != null) {
            prevNode.next = nextNode;
        }
        if (nextNode != null) {         // +
            nextNode.prev = prevNode;   // +
        }                               // +
    }
    

    第三处:修改释放处,添加释放prev指针域。

    //释放链表指定结点
    public void releaseNode(Node node) {
        if (node != null) {
            node.prev = null;   // +
            node.data = null;
            node.next = null;
        }
    }
    

    到此,双向链表的设计和实现就学完了,但是既然存在双向链表,那么肯定还有一些方法可以简化,接下来,我们需要对一些特殊的方法进行优化。

    4.02、获取位置之前结点

    //获取位置之前结点
    private Node getIndexPre(int index) {
        return getIndex(index).prev;
    }
    

    4.03、删除链表最后结点

    //删除链表最后结点(需要考虑last指向问题)
    public void removeLast() {
        //判断链表是否为空
        if (isEmpty()) {
            return;
        }
        //获取链表最后节点
        Node lastNode = last;
        //删除链表最后结点
        Node prevNode = lastNode.prev;
        prevNode.next = null;
        //释放最后节点指向
        releaseNode(lastNode);
        //修改last的指向
        last = prevNode;
        //让链表的长度减一
        size--;
    }
    

    4.04、逆序查找数据首次出现位置

    //逆序查找数据首次出现位置
    public int lastIndexOf(E e) {
        //判断链表是否为空
        if (isEmpty()) {
            return -1;
        }
        //判断对象是否为空
        if (e == null) {
            return -1;
        }
        //获取指定位置结点
        Node curNode = last;
        for (int i = 0; curNode != null; i++) {
            if (e.equals(curNode.data)) {
                return i;
            }
            curNode = curNode.prev;
        }
        //没有找到返回负一
        return -1;
    }
    

    第五章 单向循环链表介绍

    单向循环链表是另一种形式的链式存储结构,它的特点是表中最后一个结点的指针域指向头结点,整个链表形成一个环。

    第六章 单向循环链表实现

    6.01、定义链表的结点类

    /**
     * 单向循环链表实现代码
     */
    public class SinglyCircularLinkedList<E> {
        //定义结点类
        public class Node {
            E data;     //代表结点数据
            Node next;  //指向下个结点
    
            public Node(E data) {
                this.data = data;
            }
    
            @Override
            public String toString() {
                return "Node{data=" + data + "}";
            }
        }
    
        //下节内容写这...
    }
    

    6.02、定义链表的属性值

    /**
     * 单向循环链表实现代码
     */
    public class SinglyCircularLinkedList<E> {
        //省略以上代码...
        
        private Node head;  //代表链表头部
        private Node last;  //代表链表尾部
        private int size;   //代表链表长度    
    
        //下节内容写这...
    }
    

    6.03、初始化各个属性值

    /**
     * 单向链表实现代码
     */
    public class SinglyLinkedList<E> {
        //省略以上代码...
    
        public SinglyCircularLinkedList() {
            //头结点应该指向第一个结点,现在没有,所以为null
            this.head = null;
            //尾结点应该指向最后的结点,现在没有,所以为null
            this.last = null;
            this.size = 0;
        }
    
        //下节内容写这...
    }
    

    6.04、获取链表当前大小

    //获取链表当前大小
    public int size() {
        return size;
    }
    

    6.05、判断链表是否为空

    //判断链表是否为空
    public boolean isEmpty() {
        return size == 0;
    }
    

    6.06、检查下标是否合法

    //检查下标是否合法
    public void checkIndex(int index) {
        if (index < 0 || (size - 1) < index) {
            throw new IndexOutOfBoundsException("链表下标越界异常,请检查链表的下标!");
        }
    }
    

    6.07、连接链表两个结点

    //连接链表两个结点
    public void connectNode(Node prevNode, Node nextNode) {
        if (prevNode != null) {
            prevNode.next = nextNode;
        }
    }
    

    6.08、释放链表指定结点

    //释放链表指定结点
    public void releaseNode(Node node) {
        if (node != null) {
            node.data = null;
            node.next = null;
        }
    }
    

    6.09、返回链表最后结点

    //返回链表最后结点
    public Node getLast() {
        //判断链表是否为空
        if (isEmpty()) {
            return null;
        }
        //返回链表最后结点
        return last;
    }
    

    6.10、返回链表首个结点

    //返回链表首个结点
    public Node getFirst() {
        //判断链表是否为空
        if (isEmpty()) {
            return null;
        }
        //返回链表首个结点
        return head;
    }
    

    6.11、获取指定位置结点

    //获取指定位置结点
    public Node getIndex(int index) {
        //检查下标是否合法
        checkIndex(index);
        //获取指定位置结点
        Node curNode = head;
        for (int i = 0; i < index; i++) {
            curNode = curNode.next;
        }
        //返回指定位置结点
        return curNode;
    }
    

    6.12、获取位置之前结点

    //获取位置之前结点
    private Node getIndexPre(int index) {
        //检查下标是否合法
        checkIndex(index);
        //获取首结点前结点
        if (index == 0) {
            return last;
        }
        //获取位置之前结点
        Node preNode = head;
        for (int i = 0; i < (index - 1); i++) {
            preNode = preNode.next;
        }
        //返回位置之前结点
        return preNode;
    }
    

    6.13、链表尾后添加数据

    默认为空的时候,头指针head和尾指针last均指向null

    若是为空的时候,添加完数据应该自己指向自己,自我成环。

    非空添加数据,我们直接向last指向结点后追加结点即可。


    方法实现:

    //链表尾后添加数据
    public void addLast(E e) {
        //判断链表是否为空
        if (isEmpty()) {
            //创建新的结点
            Node newNode = new Node(e);
            //修改头尾指向
            head = newNode;
            last = newNode;
            //自己连接自己
            connectNode(newNode, newNode);
        } else {
            //获取last结点
            Node oldLast = last;
            //创建新的结点
            Node newLast = new Node(e);
            //修改last指向
            last = newLast;
            //头尾连接成环
            connectNode(oldLast, newLast);
            connectNode(newLast, head);
        }
        //链表链表长度加一
        size++;
    }
    

    方法测试:

    public class SinglyCircularLinkedListTest {
        public static void main(String[] args) {
            SinglyCircularLinkedList<String> linkedList = new SinglyCircularLinkedList<>();
    
            linkedList.addLast("张三");
            linkedList.addLast("李四");
            linkedList.addLast("王五");
    
            System.out.println("==========打印链表基本信息:");
            System.out.println("链表结点个数:" + linkedList.size());
            System.out.println("链表是否为空:" + linkedList.isEmpty());
            System.out.println("==========打印链表所有结点:");
            for (int i = 0; i < linkedList.size(); i++) {
                System.out.println(linkedList.getIndex(i));
            }
            System.out.println("==========打印链表首尾结点:");
            System.out.println("链表的头结点:" + linkedList.getFirst());
            System.out.println("链表的尾结点:" + linkedList.getLast());
        }
    }
    

    运行结果:

    ==========打印链表基本信息:
    链表结点个数:3
    链表是否为空:false
    ==========打印链表所有结点:
    Node{data=张三}
    Node{data=李四}
    Node{data=王五}
    ==========打印链表首尾结点:
    链表的头结点:Node{data=张三}
    链表的尾结点:Node{data=王五}
    

    6.14、链表头后添加数据

    方法实现:

    //链表头后添加数据
    public void addFirst(E e) {
        //判断链表是否为空
        if (isEmpty()) {
            addLast(e);
            return;
        } else {
            //获取head结点
            Node oldHead = head;
            //创建新的结点
            Node newHead = new Node(e);
            //修改head指向
            head = newHead;
            //头尾连接成环
            connectNode(last, newHead);
            connectNode(newHead, oldHead);
        }
        //链表链表长度加一
        size++;
    }
    

    方法测试:

    public class SinglyCircularLinkedListTest {
        public static void main(String[] args) {
            SinglyCircularLinkedList<String> linkedList = new SinglyCircularLinkedList<>();
    
            linkedList.addFirst("张三");
            linkedList.addFirst("李四");
            linkedList.addFirst("王五");
    
            System.out.println("==========打印链表基本信息:");
            System.out.println("链表结点个数:" + linkedList.size());
            System.out.println("链表是否为空:" + linkedList.isEmpty());
            System.out.println("==========打印链表所有结点:");
            for (int i = 0; i < linkedList.size(); i++) {
                System.out.println(linkedList.getIndex(i));
            }
            System.out.println("==========打印链表首尾结点:");
            System.out.println("链表的头结点:" + linkedList.getFirst());
            System.out.println("链表的尾结点:" + linkedList.getLast());
        }
    }
    

    运行结果:

    ==========打印链表基本信息:
    链表结点个数:3
    链表是否为空:false
    ==========打印链表所有结点:
    Node{data=王五}
    Node{data=李四}
    Node{data=张三}
    ==========打印链表首尾结点:
    链表的头结点:Node{data=王五}
    链表的尾结点:Node{data=张三}
    

    6.15、指定位置添加数据

    方法实现:

    //指定位置添加数据
    public void addIndex(int index, E e) {
        //获取位置之前结点
        Node preNode = getIndexPre(index);
        //获取指定位置结点
        Node curNode = preNode.next;
        //创建一个新的结点
        Node newNode = new Node(e);
        //开始三个结点连接
        connectNode(preNode, newNode);
        connectNode(newNode, curNode);
        //修改head的指向
        if (curNode == head) {
            head = newNode;
        }
        //当前链表长度加一
        size++;
    }
    

    方法测试:

    public class SinglyCircularLinkedListTest {
        public static void main(String[] args) {
            SinglyCircularLinkedList<String> linkedList = new SinglyCircularLinkedList<>();
    
            linkedList.addLast("张三");
            linkedList.addLast("李四");
            linkedList.addLast("王五");
    
            linkedList.addIndex(0, "张三长辈");
            linkedList.addIndex(linkedList.size() - 1, "王五长辈");
    
            System.out.println("==========打印链表基本信息:");
            System.out.println("链表结点个数:" + linkedList.size());
            System.out.println("链表是否为空:" + linkedList.isEmpty());
            System.out.println("==========打印链表所有结点:");
            for (int i = 0; i < linkedList.size(); i++) {
                System.out.println(linkedList.getIndex(i));
            }
            System.out.println("==========打印链表首尾结点:");
            System.out.println("链表的头结点:" + linkedList.getFirst());
            System.out.println("链表的尾结点:" + linkedList.getLast());
        }
    }
    

    运行结果:

    ==========打印链表基本信息:
    链表结点个数:5
    链表是否为空:false
    ==========打印链表所有结点:
    Node{data=张三长辈}
    Node{data=张三}
    Node{data=李四}
    Node{data=王五长辈}
    Node{data=王五}
    ==========打印链表首尾结点:
    链表的头结点:Node{data=张三长辈}
    链表的尾结点:Node{data=王五}
    

    6.16、删除指定位置结点

    方法实现:

    //删除指定位置结点
    public void removeIndex(int index) {
        //获取位置之前结点
        Node preNode = getIndexPre(index);
        //获取指定位置结点
        Node curNode = preNode.next;
        //获取位置之后结点
        Node nexNode = curNode.next;
        //如果只有一个结点
        if (size == 1) {
            //修改head的指向
            head = null;
            //修改last的指向
            last = null;
            //释放链表指定结点
            releaseNode(preNode);
            releaseNode(curNode);
            releaseNode(nexNode);
            //当前链表长度减一
            size--;
        } else {
            //修改head的指向
            if (curNode == head) {
                head = nexNode;
            }
            //修改last的指向
            if (curNode == last) {
                last = preNode;
            }
            //删除指定位置结点
            connectNode(preNode, nexNode);
            //释放链表指定结点
            releaseNode(curNode);
            //当前链表长度减一
            size--;
        }
    }
    

    方法测试:

    public class SinglyCircularLinkedListTest {
        public static void main(String[] args) {
            SinglyCircularLinkedList<String> linkedList = new SinglyCircularLinkedList<>();
    
            linkedList.addLast("张三");
            linkedList.addLast("李四");
            linkedList.addLast("王五");
    
            linkedList.removeIndex(0);
            linkedList.removeIndex(linkedList.size() - 1);
    
            System.out.println("==========打印链表基本信息:");
            System.out.println("链表结点个数:" + linkedList.size());
            System.out.println("链表是否为空:" + linkedList.isEmpty());
            System.out.println("==========打印链表所有结点:");
            for (int i = 0; i < linkedList.size(); i++) {
                System.out.println(linkedList.getIndex(i));
            }
            System.out.println("==========打印链表首尾结点:");
            System.out.println("链表的头结点:" + linkedList.getFirst());
            System.out.println("链表的尾结点:" + linkedList.getLast());
        }
    }
    

    运行结果:

    ==========打印链表基本信息:
    链表结点个数:1
    链表是否为空:false
    ==========打印链表所有结点:
    Node{data=李四}
    ==========打印链表首尾结点:
    链表的头结点:Node{data=李四}
    链表的尾结点:Node{data=李四}
    

    6.17、删除链表首个结点

    方法实现:

    //删除链表首个结点
    public void removeFirst() {
        //判断链表是否为空
        if (isEmpty()) {
            return;
        }
        //删除链表首个结点
        removeIndex(0);
    }
    

    方法测试:

    public class SinglyCircularLinkedListTest {
        public static void main(String[] args) {
            SinglyCircularLinkedList<String> linkedList = new SinglyCircularLinkedList<>();
    
            linkedList.addLast("张三");
            linkedList.addLast("李四");
            linkedList.addLast("王五");
    
            linkedList.removeFirst();
    
            System.out.println("==========打印链表基本信息:");
            System.out.println("链表结点个数:" + linkedList.size());
            System.out.println("链表是否为空:" + linkedList.isEmpty());
            System.out.println("==========打印链表所有结点:");
            for (int i = 0; i < linkedList.size(); i++) {
                System.out.println(linkedList.getIndex(i));
            }
            System.out.println("==========打印链表首尾结点:");
            System.out.println("链表的头结点:" + linkedList.getFirst());
            System.out.println("链表的尾结点:" + linkedList.getLast());
        }
    }
    

    运行结果:

    ==========打印链表基本信息:
    链表结点个数:2
    链表是否为空:false
    ==========打印链表所有结点:
    Node{data=李四}
    Node{data=王五}
    ==========打印链表首尾结点:
    链表的头结点:Node{data=李四}
    链表的尾结点:Node{data=王五}
    

    6.18、删除链表最后结点

    方法实现:

    //删除链表最后结点
    public void removeLast() {
        //判断链表是否为空
        if (isEmpty()) {
            return;
        }
        //删除链表最后结点
        removeIndex(size - 1);
    }
    

    方法测试:

    public class SinglyCircularLinkedListTest {
        public static void main(String[] args) {
            SinglyCircularLinkedList<String> linkedList = new SinglyCircularLinkedList<>();
    
            linkedList.addLast("张三");
            linkedList.addLast("李四");
            linkedList.addLast("王五");
    
            linkedList.removeLast();
    
            System.out.println("==========打印链表基本信息:");
            System.out.println("链表结点个数:" + linkedList.size());
            System.out.println("链表是否为空:" + linkedList.isEmpty());
            System.out.println("==========打印链表所有结点:");
            for (int i = 0; i < linkedList.size(); i++) {
                System.out.println(linkedList.getIndex(i));
            }
            System.out.println("==========打印链表首尾结点:");
            System.out.println("链表的头结点:" + linkedList.getFirst());
            System.out.println("链表的尾结点:" + linkedList.getLast());
        }
    }
    

    运行结果:

    ==========打印链表基本信息:
    链表结点个数:2
    链表是否为空:false
    ==========打印链表所有结点:
    Node{data=张三}
    Node{data=李四}
    ==========打印链表首尾结点:
    链表的头结点:Node{data=张三}
    链表的尾结点:Node{data=李四}
    

    6.19、输出链表所有结点

    方法实现:

    //输出链表所有结点
    public void show() {
        //判断链表是否为空
        if (isEmpty()) {
            return;
        }
        //遍历链表所有结点
        Node curNode = head;
        do {
            System.out.println(curNode);
            curNode = curNode.next;
        } while (curNode != head);
    }
    

    方法测试:

    public class SinglyCircularLinkedListTest {
        public static void main(String[] args) {
            SinglyCircularLinkedList<String> linkedList = new SinglyCircularLinkedList<>();
    
            linkedList.addLast("张三");
            linkedList.addLast("李四");
            linkedList.addLast("王五");
    
            System.out.println("==========打印链表基本信息:");
            System.out.println("链表结点个数:" + linkedList.size());
            System.out.println("链表是否为空:" + linkedList.isEmpty());
            System.out.println("==========打印链表所有结点:");
            linkedList.show();
            System.out.println("==========打印链表首尾结点:");
            System.out.println("链表的头结点:" + linkedList.getFirst());
            System.out.println("链表的尾结点:" + linkedList.getLast());
        }
    }
    

    运行结果:

    ==========打印链表基本信息:
    链表结点个数:3
    链表是否为空:false
    ==========打印链表所有结点:
    Node{data=张三}
    Node{data=李四}
    Node{data=王五}
    ==========打印链表首尾结点:
    链表的头结点:Node{data=张三}
    链表的尾结点:Node{data=王五}
    

    6.20、反转链表所有结点

    方法实现:

    //反转链表所有结点
    public void reverse() {
        //判断链表是否为空
        if (isEmpty()) {
            return;
        }
        //创建一个临时节点
        Node newHead = new Node(null);
        //循环遍历圆环结点
        Node newFirst;
        Node tmpNode;
        Node curNode = head;
        do {
            //缓存当前结点下个结点
            tmpNode = curNode.next;
            //获取临时结点首结点
            newFirst = newHead.next;
            //开始三个结点进行关联
            connectNode(newHead, curNode);
            connectNode(curNode, newFirst);
            //让当前的结点往后移动
            curNode = tmpNode;
        } while (curNode != head);
        //交换旧头尾指向
        tmpNode = head;
        head = last;
        last = tmpNode;
        //首尾相连成圆环
        connectNode(last, newHead.next);
        //释放新建临时节点
        releaseNode(newHead);
    }
    

    方法测试:

    public class SinglyCircularLinkedListTest {
        public static void main(String[] args) {
            SinglyCircularLinkedList<String> linkedList = new SinglyCircularLinkedList<>();
    
            linkedList.addLast("张三");
            linkedList.addLast("李四");
            linkedList.addLast("王五");
    
            linkedList.reverse();
    
            System.out.println("==========打印链表基本信息:");
            System.out.println("链表结点个数:" + linkedList.size());
            System.out.println("链表是否为空:" + linkedList.isEmpty());
            System.out.println("==========打印链表所有结点:");
            linkedList.show();
            System.out.println("==========打印链表首尾结点:");
            System.out.println("链表的头结点:" + linkedList.getFirst());
            System.out.println("链表的尾结点:" + linkedList.getLast());
        }
    }
    

    运行结果:

    ==========打印链表基本信息:
    链表结点个数:3
    链表是否为空:false
    ==========打印链表所有结点:
    Node{data=王五}
    Node{data=李四}
    Node{data=张三}
    ==========打印链表首尾结点:
    链表的头结点:Node{data=王五}
    链表的尾结点:Node{data=张三}
    

    6.21、清空链表所有结点

    方法实现:

    //清空链表所有结点
    public void clear() {
        //判断链表是否为空
        if (isEmpty()) {
            return;
        }
        //遍历链表所有结点
        Node tmpNode;
        Node curNode = head;
        do {
            //缓存下个结点
            tmpNode = curNode.next;
            //释放当前结点
            releaseNode(curNode);
            //移动下个结点
            curNode = tmpNode;
        } while (curNode != head);
        //重置链表基本信息
        head = null;
        last = null;
        size = 0;
    }
    

    方法测试:

    public class SinglyCircularLinkedListTest {
        public static void main(String[] args) {
            SinglyCircularLinkedList<String> linkedList = new SinglyCircularLinkedList<>();
    
            linkedList.addLast("张三");
            linkedList.addLast("李四");
            linkedList.addLast("王五");
    
            linkedList.clear();
    
            System.out.println("==========打印链表基本信息:");
            System.out.println("链表结点个数:" + linkedList.size());
            System.out.println("链表是否为空:" + linkedList.isEmpty());
            System.out.println("==========打印链表所有结点:");
            linkedList.show();
            System.out.println("==========打印链表首尾结点:");
            System.out.println("链表的头结点:" + linkedList.getFirst());
            System.out.println("链表的尾结点:" + linkedList.getLast());
        }
    }
    

    运行结果:

    ==========打印链表基本信息:
    链表结点个数:0
    链表是否为空:true
    ==========打印链表所有结点:
    ==========打印链表首尾结点:
    链表的头结点:null
    链表的尾结点:null
    

    6.22、顺序查找数据首次出现位置

    方法实现:

    //顺序查找数据首次出现位置
    public int indexOf(E e) {
        //判断链表是否为空
        if (isEmpty()) {
            return -1;
        }
        //判断对象是否为空
        if (e == null) {
            return -1;
        }
        //获取指定位置结点
        Node curNode = head;
        for (int i = 0; i < size; i++) {
            if (e.equals(curNode.data)) {
                return i;
            }
            curNode = curNode.next;
        }
        //没有找到返回负一
        return -1;
    }
    

    方法测试:

    public class SinglyCircularLinkedListTest {
        public static void main(String[] args) {
            SinglyCircularLinkedList<String> linkedList = new SinglyCircularLinkedList<>();
    
            linkedList.addLast("张三");
            linkedList.addLast("李四");
            linkedList.addLast("王五");
    
            System.out.println(linkedList.indexOf("张三"));
            System.out.println(linkedList.indexOf("李四"));
            System.out.println(linkedList.indexOf("王五"));
    
            System.out.println("==========打印链表基本信息:");
            System.out.println("链表结点个数:" + linkedList.size());
            System.out.println("链表是否为空:" + linkedList.isEmpty());
            System.out.println("==========打印链表所有结点:");
            linkedList.show();
            System.out.println("==========打印链表首尾结点:");
            System.out.println("链表的头结点:" + linkedList.getFirst());
            System.out.println("链表的尾结点:" + linkedList.getLast());
        }
    }
    

    运行结果:

    0
    1
    2
    ==========打印链表基本信息:
    链表结点个数:3
    链表是否为空:false
    ==========打印链表所有结点:
    Node{data=张三}
    Node{data=李四}
    Node{data=王五}
    ==========打印链表首尾结点:
    链表的头结点:Node{data=张三}
    链表的尾结点:Node{data=王五}
    

    6.23、逆序查找数据首次出现位置

    方法实现:

    //逆序查找数据首次出现位置
    public int lastIndexOf(E e) {
        //判断链表是否为空
        if (isEmpty()) {
            return -1;
        }
        //判断对象是否为空
        if (e == null) {
            return -1;
        }
        //反转当前链表结点
        reverse();
        //获取指定位置结点
        int index = indexOf(e);
        //反转当前链表结点
        reverse();
        //返回数据指定位置
        return index;
    }
    

    方法测试:

    public class SinglyCircularLinkedListTest {
        public static void main(String[] args) {
            SinglyCircularLinkedList<String> linkedList = new SinglyCircularLinkedList<>();
    
            linkedList.addLast("张三");
            linkedList.addLast("李四");
            linkedList.addLast("王五");
    
            System.out.println(linkedList.lastIndexOf("张三"));
            System.out.println(linkedList.lastIndexOf("李四"));
            System.out.println(linkedList.lastIndexOf("王五"));
    
            System.out.println("==========打印链表基本信息:");
            System.out.println("链表结点个数:" + linkedList.size());
            System.out.println("链表是否为空:" + linkedList.isEmpty());
            System.out.println("==========打印链表所有结点:");
            linkedList.show();
            System.out.println("==========打印链表首尾结点:");
            System.out.println("链表的头结点:" + linkedList.getFirst());
            System.out.println("链表的尾结点:" + linkedList.getLast());
        }
    }
    

    运行结果:

    2
    1
    0
    ==========打印链表基本信息:
    链表结点个数:3
    链表是否为空:false
    ==========打印链表所有结点:
    Node{data=张三}
    Node{data=李四}
    Node{data=王五}
    ==========打印链表首尾结点:
    链表的头结点:Node{data=张三}
    链表的尾结点:Node{data=王五}
    

    第七章 双向循环链表介绍

    双向循环链表是另一种形式的链式存储结构,它的特点是表中最后一个结点的指针域指向头结点,头结点的指针域指向最后一个结点,整个链表形成一个环。

    第八章 双向循环链表实现

    8.01、再看代码如此多娇

    我们已经学过了单向循环链表的设计和实现了,双向循环链表只需要在单向循环链表的基础上添加三行代码就能实现,你看神奇不神奇。

    我们需要直接拷贝SinglyCircularLinkedListDoublyCircularLinkedList,然后拷贝SinglyCircularLinkedListTestDoublyCircularLinkedListTest,并修改相对应的构造方法名称。

    第一处:修改节点类,添加prev指针域。

    //定义结点类
    public class Node {
        Node prev;  //指向上个结点 +
        E data;     //代表结点数据
        Node next;  //指向下个结点
    
        public Node(E data) {
            this.data = data;
        }
    
        @Override
        public String toString() {
            return "Node{data=" + data + "}";
        }
    }
    

    第二处:修改连接处,添加指向上个结点。

    //连接链表两个结点
    public void connectNode(Node prevNode, Node nextNode) {
        if (prevNode != null) {
            prevNode.next = nextNode;
        }
        if (nextNode != null) {         // +
            nextNode.prev = prevNode;   // +
        }                               // +
    }
    

    第三处:修改释放处,添加释放prev指针域。

    //释放链表指定结点
    public void releaseNode(Node node) {
        if (node != null) {
            node.prev = null;   // +
            node.data = null;
            node.next = null;
        }
    }
    

    到此,双向循环链表的设计和实现就学完了,但是既然存在双向循环链表,那么肯定还有一些方法可以简化,接下来,我们需要对一些特殊的方法进行优化。

    8.02、获取位置之前结点

    //获取位置之前结点
    private Node getIndexPre(int index) {
        return getIndex(index).prev;
    }
    

    8.03、删除链表最后结点

    //删除链表最后结点
    public void removeLast() {
        //判断链表是否为空
        if (isEmpty()) {
            return;
        }
        //获取位置之前结点
        Node preNode = last.prev;
        //获取指定位置结点
        Node curNode = last;
        //获取位置之后结点
        Node nexNode = last.next;
        //如果只有一个结点
        if (size == 1) {
            //修改head的指向
            head = null;
            //修改last的指向
            last = null;
            //释放链表指定结点
            releaseNode(preNode);
            releaseNode(curNode);
            releaseNode(nexNode);
            //当前链表长度减一
            size--;
        } else {
            //修改head的指向
            if (curNode == head) {
                head = nexNode;
            }
            //修改last的指向
            if (curNode == last) {
                last = preNode;
            }
            //删除指定位置结点
            connectNode(preNode, nexNode);
            //释放链表指定结点
            releaseNode(curNode);
            //当前链表长度减一
            size--;
        }
    }
    

    8.04、逆序查找数据首次出现位置

    //逆序查找数据首次出现位置
    public int lastIndexOf(E e) {
        //判断链表是否为空
        if (isEmpty()) {
            return -1;
        }
        //判断对象是否为空
        if (e == null) {
            return -1;
        }
        //获取指定位置结点
        Node curNode = last;
        for (int i = 0; i < size; i++) {
            if (e.equals(curNode.data)) {
                return i;
            }
            curNode = curNode.prev;
        }
        //没有找到返回负一
        return -1;
    }
    
    展开全文
  • 数据结构实验三-有关线性链表的操作,建立线性链表,初始化线性链表,插入元素,删除元素,清空线性链表,摧毁线性链表
  • 数据结构线性链表操作 链表结点的增添 删除
  • 线性表 目录 线性表 顺序表 单链表 线性链表的变形 循环链表 双向链表 顺序表的优缺点 特点逻辑结构上相邻的元素其物理结构也相邻 查找删除插入算法:与表的大小呈线性的关系 优点存取操作速度快 缺点空间的低效利用...
  • 数据结构线性表单链表的查找、插入、删除.doc
  • 数据结构线性链表

    2015-06-28 18:56:55
    数据结构实现C++线性链表,实现增删改查基本方法
  • 数据结构和算法的关系 ➢数据data结 构(structure)是一门研究组织数据方式的...数据结构包括:线性结构和非线性结构线性结构 1)线性结构作为最常用的数据结构,其特点是数据元素之间存在- -对- - 的线性关系(a[0]=3

    数据结构

    结构,简单的理解就是关系,些如分子结构,就是说组成分子的原子之间的排到方式。严格点说,结构是指各个组成部分相互搭配和排的方式。在现实世界中,不同数据元素之间不是独立的,而是存在特定的关系,我们将这些关系称为结构。那数据结构是什么?
    数据结构:是相互之间存在一种或多种特定关系的数据元素的集合。
    在计算机虫,数据元素并不是孤立、杂乱无序的,而是具有内在联系的数据集合。数据元素之间存在的一种或多种特定关系,也就是数
    据的组织形式。
    为编写出-个好"的程序,必须分析待处理对象的特性及各处理对象之间存在的关系。这也就是研究数据结构的意义所在。

    数据结构分为逻辑结构和物理结构

    在这里插入图片描述

    逻辑结构

     逻辑结构:是指数据对象中数据元素之间的相互关系。其实这也是我们今后最需要关注的问题。逻辑结构分为以下四种:

    1.集合结构:

    集合结构:集合结构中的数据元素除了同属于一个集合外它们之间没有其他关系。各个数据元素是“平等"的,它们的共同属性是"同属
    于一个集合”。数据结构中的集合关系就类似于数学中的集合
    在这里插入图片描述

    2 线性结构:

    数据元素之间一对一的关系
    在这里插入图片描述

    3.树状结构:

    数据元素之间存在一对多的关系
    在这里插入图片描述

    4.图形结构:

    数据中的元素是多对多的关系
    在这里插入图片描述

    物理结构:

    说完了逻辑结构,我们再来说说数据的物理结构(很多书中也叫做存储结构,你只要在理解上把它们当回事就可以了)。
    物理结构:是指数据的逻辑结构在计算机中的存储形式。
    数据是数据元素的集合,那么根据物理结构的定义,实际上就是如何把数据元素存储到计算机的存储器中。存储器主要是针对内存而言
    的,像硬盘、软盘、光盘等外部存储器的数据组织通常用文件结构来描述。
    数据的存储结构应正确反映数据元素之间的逻辑关系,这才是最为关键的,如何存储数据元素之间的逻辑关系,是实现物理结构的重点
    和难点。
    数据元素的存储结构形式有两种:顺序存储和链式存储。
    1.顺序存储结构
    顺序存储结构:是把数据元素存放在地址连续的存储单元里,其数据间的逻辑关系和物理关系是一致的(如图所示)。
    在这里插入图片描述这种存储结构其实很简单,说自了,就是排队点位。大家都按顺序排好,每个人点一小段空间,大家谁也别插谁的队。我们之前学计算
    机语言时,数组就是这样的顺序存储结构。当你告诉计算机,你要建立一一个有9个整型数据的数组时,计算机就在内存中找了片空地,按
    照一个整型所占位置的大小乘以9,开辟一段连续的空间, 于是第一个数组数据就放在第一个位置, 第二个数据放在第二个,这样依次摆放。
    2.链式存储结构
    如果就是这么简单和有规律。一切就好办了。可实际上2总会有也会有人要上厕所:有人会放弃排队。所以这个队伍中会添加等成员,也有可能会去掉老元素,整个结构时刻都处于变化中,显然面对这样时常要变化的结构,顺序存储是不科学的。那怎么办呢?
    现在如银行、医院等地方,设置了排队系统,也就是每个人去了。先领一个号,等着叫号,叫到时去办理业务或看病。在等待的时候,你爱在哪在哪,可以坐着、站着或者走动,甚至出去涟一圈,只要及时回来就行。你关注的是前一个号有没有被响到,响到了,下一个就轮到了。
    链式存储结构是把数据示素存放在任意的存储单元黑,这组存储单元可以是连续的,也可以是否连续的。数据元素的存储关系并不能及映其逻辑关系,因此需要用一个指针存放数据元素的地址;这样通过地址就可以我到相关联数据元素的位置(如图1-5-6所示)。
    在这里插入图片描述

    数据结构和算法的关系

    ➢数据data结 构(structure)是一门研究组织数据方式的学科,有了编程语言也就有了
    数据结构.学好数据结构可以编写出更加漂亮更加有效率的代码。
    ➢要学习好数据结构就要多多考虑如何将生活中遇到的问题,用程序去实现解决.
    ➢程序=数据结构+算法
    ➢数据结构是算法的基础,换言之,想要学好算法,需要把数据结构学到位。

    线性链表和非线性链表

    数据结构包括:线性结构和非线性结构。
    线性结构
    1)线性结构作为最常用的数据结构,其特点是数据元素之间存在- -对- - 的线性关系(a[0]=30)
    2)线性结构有两种不同的存储结构,即顺序存储结构(最经典数组)和链式存储结构(经典链表)。顺序存储的线性表称为顺序表,顺序表中的存储元素是连续的。(指存储元素的地址是连续的)
    3)链式存储的线性表称为链表,链表中的存储元素不一定是连续的,元素节点中存放数据元素以及相邻元素的地址信息
    4)线性结构常见的有:数组、队列、链表和栈,后面我们会详细讲解.

    非线性结构
    非线性结构包括:二 维数组, 多维数组, 广义表,树结构,图结构

    稀疏数组和队列

    稀疏Sparsearray数组

    在这里插入图片描述基本介绍
    当一个数组中大部分元素为0,或者为同一个值的数组时,可以使用稀疏数组来保存该数组。
    稀疏数组的处理方法是: .
    1)记录数组一共有几行几列,有多少个不同的值
    2)把具有不同值的元素的行列及值记录在一个小规模的数组中,从而缩小程序的规模
    在这里插入图片描述右图的第一行【0】的6是一共6行,7一共7列,8指一共8个值
    原来的数组是67=42大小的数组,可以将其变成93=27的稀疏数组

    应用实例
    1)使用稀疏数组,来保留类似前面的二维数组(棋盘、地图等等)
    2)把稀疏数组存盘,并且可以从新恢复原来的二维数组数
    3)整体思路分析

    在这里插入图片描述代码实现:

    public class Sparcesearray {
        public static void main(String[] args) {
    
            //第一步   创建一个11*11的二维数组
            //给二维数组中添加棋子
            //1 表示黑子,2表示蓝色的,0表示没有棋子
    
            int cheersArray[][] = new int[11][11];
            cheersArray[1][2] =1;
            cheersArray[2][3] =2;
            cheersArray[4][5] =2;
    
            for (int[] ints : cheersArray) {
                for (int i : ints) {
                    System.out.print("\t"+i);
                }
                System.out.println();
            }
    
            // 获取二维数组中元素不为0的个数  sum
    
            int sum=0;
            for (int i = 0; i < 11; i++) {
                for (int j = 0; j < 11; j++) {
                    if (cheersArray[i][j]!=0){
                        sum++;
                    }
                }
            }
            System.out.println("sum个数是"+sum);
    
            //创建稀疏数组
            int specArray[][] =new int[sum+1 ][3];
            specArray[0][0] =11;
            specArray[0][1] =11;
            specArray[0][2] =sum;
            //将二维数组中不为0的数放入到稀疏数组中去
            int count=0;
            for (int i = 0; i < 11; i++) {
                for (int j = 0; j < 11; j++) {
                    if (cheersArray[i][j]!=0){
                        count++;
                      specArray[count][0]=i;
                      specArray[count][1]=j;
                      specArray[count][2]=cheersArray[i][j];
                    }
                }
            }
    
            System.out.println("二维数组变成的稀疏数组是:");
            for (int[] ints : specArray) {
                for (int anInt : ints) {
                    System.out.print("\t"+anInt);
                }
                System.out.println();
            }
    
            System.out.println("稀疏数组再次变为原来的二维数组是");
            //第三步将稀疏数组再次变成二维数组
            int cheersArray2[][] =new int[specArray[0][0]] [specArray[0][1]];
    
            //将稀疏数组中的值再次赋值给二维数组(循环从1开始,因为稀疏数组从第二行开始才是值)
            for (int i = 1; i <specArray.length ; i++) {
                cheersArray2[specArray[i][0]][specArray[i][1]] =specArray[i][2];
            }
            for (int[] ints : cheersArray2) {
                for (int anInt : ints) {
                    System.out.print("\t"+anInt);
                }
                System.out.println();
            }
        }
    }
    

    队列

    队列介绍
    1)队列是一个有序列表,可以用数组或是链表来实现。
    2)遵循先入先出的原则。即:先存入队列的数据,要先取出。后存入的要后取出
    3)示意图:
    在这里插入图片描述数组模拟队列思路
    队列本身是有序列表,若使用数组的结构来存储队列的数据,则队列数组的声明如下图,其中maxSize是该队列的最大容量。
    因为队列的输出、输入是分别从前后端来处理,因此需要两个变量front及rear分别记录队列前后端的下标,front会随着数据输出而改变,而rear则是随着数据输入而改变,如图所示
    当我们将数据存入队列时称为”addQueue”,addQueue的处理需要有两个步骤:思路分析
    1)将尾指针往后移:rear+1,当front == rear【空】
    2)若尾指针rear小于队列的最大下标maxSize-1,则将数据存入rear所指的数组元素中,否则无法存入数据。rear==maxSize-1[队列满]

    //使用数组模拟队列
    public class ArrayQueue {
        private int maxSize;//队列最大的大小
        private int front;//指向队列的头
        private int real;//指向队列的尾部
        private int array[];//该数组用于数据的存储,模拟队列的存取
    
        //创建队列的构造器
        public ArrayQueue(int arraymaxSize){
            maxSize=arraymaxSize;
            array=new int[maxSize];
            front=-1;//指向队列头部的前一个位置
            real=-1;//指向队列尾部的数据(可能是队列最后一个数据)
        }
        //是否是满的
        public Boolean isFull(){
            return real ==maxSize-1;
        }
        //是否是空的
        public Boolean isEmpty(){
            return  front==real;
        }
        //向队列中添加数据
        public void addQueue(int n){
            if (isFull()){
                System.out.println("对不起队列满了不能加入数据");
                return;
            }
            real++;//尾部后移
            array[real]=n;
        }
        public int getQueue(){
            if (isEmpty()){
                throw new RuntimeException("对不起,队列没有数据可取");
            }
            front++;//让front后移
            return array[front];
    
        }
        //显示所有的队列数据
        public void list(){
            if (isEmpty()){
                System.out.println("队列中没有数据,请先插入数据");
            }
            for (int i = 0; i <array.length ; i++) {
                System.out.println(+array[i]);
            }
        }
        //查看队列头部的数据
        public int peak(){
            if (isEmpty()){
                throw new RuntimeException("队列中,没有数据请先插入数据");
            }
            return array[front+1];
        }
    
    
        public static void main(String[] args) {
            ArrayQueue queue = new ArrayQueue(3);
    
            Boolean loop=true;
            char key =' ';
            Scanner scanner = new Scanner(System.in);
    
            while(loop){
                System.out.println("s(show) :显示对列");
                System.out.println("e(exit) :退出对列");
                System.out.println("a(add) :添加对列");
                System.out.println("g(get) :获取对列的值");
                System.out.println("h(head) :查看队列头部的值");
               key= scanner.next().charAt(0);
               switch (key){
                   case 's':
                       queue.list();
                       break;
                   case 'e':
                       scanner.close();
                       loop=false;
                       break;
                   case 'a':
                       System.out.println("请输入一个数字");
                       int value =scanner.nextInt();
                       queue.addQueue(value);
                       break;
                   case 'g':
                       try{
                        int res =queue.getQueue();
                           System.out.println("取出的数据是"+res);
    
                       }catch (Exception e){
                           e.printStackTrace();
                       }
                       break;
                   case 'h':
                       try {
                         int head =   queue.peak();
                           System.out.println("查看头部的数据是"+head);
                       }catch (Exception e){
                           e.printStackTrace();
                       }
                       break;
                   default:break;
               }
            }
            System.out.println("程序退出");
        }
    }
    

    问题分析及优化:
    目前这个数组,只能一次使用,后面不能复用;
    接下来我们要用一个算法实现数组的循环使用,改进成一个环形数组取模%

    数组模拟环形队列

    对前面的数组模拟队列的优化,充分利用数组.因此将数组看做是一个环形的。(通过取模的方式来实现即可)
    分析说明:
    1)尾索引的下一个为头索引时表示队列满,即将队列容量空出一个作为约定,这个在做判断队列满的时候需要注意(rear+1)%maxSize == front满]
    2)rear==front[空]
    3)分析示意图:
    在这里插入图片描述代码实现:

    class CircleArray{
    
         int maxSize;//队列最大的大小
        //front指向队列的第一个元素
            //front=0;
        int front;//指向队列的头
        //real指向队列最后一个元素的下一个位置
        //real=0;
        int real;//指向队列的尾部
        private int array[];//该数组用于数据的存储,模拟队列的存取
    
        public  CircleArray(int arrymaxSize){
            maxSize=arrymaxSize;
            array=new int[maxSize];
        }
        //是否是满的
        public Boolean isFull(){
            return ( real +1) % maxSize==front;
        }
        //是否是空的
        public Boolean isEmpty(){
            return  front==real;
        }
        //向队列中添加数据
        public void addQueue(int n){
            if (isFull()){
                System.out.println("对不起队列满了不能加入数据");
                return;
            }
            array[real]=n;
            real=(real+1) % maxSize;
        }
        //从队列中取出数据
        public int getQueue(){
            if (isEmpty()){
                throw new RuntimeException("对不起,队列没有数据可取");
            }
            //这里我们分析到front指向的默认是第一个元素
            //第一步先将array【front】取出,保存在临时变量里
            //第二步front后移
            //第三步返回临时的变量
           int value= array[front];
            front=(front+1)%maxSize;
            return  value;
        }
        //显示所有的队列数据
        public void list(){
            if (isEmpty()){
                System.out.println("队列中没有数据,请先插入数据");
            }
            for (int i = front; i <front+numbers() ; i++) {
                System.out.println("循环队列的数据是:"+i%maxSize+array[i]);
            }
        }
        //计算出当前有效数据的个数
        public int numbers(){
            return (real+maxSize-front)%maxSize;
        }
        //查看队列头部的数据
        public int peak(){
            if (isEmpty()){
                throw new RuntimeException("队列中,没有数据请先插入数据");
            }
            return array[front];
        }
    
        public static void main(String[] args) {
    
            CircleArray queue = new CircleArray(3);
    
            Boolean loop=true;
            char key =' ';
            Scanner scanner = new Scanner(System.in);
    
            while(loop){
                System.out.println("s(show) :显示对列");
                System.out.println("e(exit) :退出对列");
                System.out.println("a(add) :添加对列");
                System.out.println("g(get) :获取对列的值");
                System.out.println("h(head) :查看队列头部的值");
                key= scanner.next().charAt(0);
                switch (key){
                    case 's':
                        queue.list();
                        break;
                    case 'e':
                        scanner.close();
                        loop=false;
                        break;
                    case 'a':
                        System.out.println("请输入一个数字");
                        int value =scanner.nextInt();
                        queue.addQueue(value);
                        break;
                    case 'g':
                        try{
                            int res =queue.getQueue();
                            System.out.println("取出的数据是"+res);
    
                        }catch (Exception e){
                            e.printStackTrace();
                        }
                        break;
                    case 'h':
                        try {
                            int head =   queue.peak();
                            System.out.println("查看头部的数据是"+head);
                        }catch (Exception e){
                            e.printStackTrace();
                        }
                        break;
                    default:break;
                }
            }
            System.out.println("程序退出");
        }
    }
    
    

    链表(Linked List)

    链表是有序的列表,但是它在内存中是存储如下小结上图:
    在这里插入图片描述
    1)链表是以节点的方式来存储,是链式存储
    2)每个节点包含data域,next域:指向下一个节点
    .3)如图:发现链表的各个节点不一定是连续存储.
    4)链表分带头节点的链表和没有头节点的链表,根据实际的需求来确定单链表(带头结点)逻辑结构示意图如下
    在这里插入图片描述1)第一种方法在添加英雄时,直接添加到链表的尾部思路分析示意图:
    在这里插入图片描述

    2)第二种方式在添加英雄时,根据排名将英雄插入到指定位置(如果有这个排名,则添加失败,并给出提示)思路的分析示意图:
    在这里插入图片描述

    3)修改节点功能思路(1)先找到该节点,通过遍历,(2)temp.name=newHeroNode.name;temp.nickname=newHeroNode.nickname
    4)删除节点
    5)代码实现

    package com.zy.LinkedList;
    /**
     * Created by MR.ZHANG on 2020/8/6 20:06
     */
    public class SingleLikedList {
        //先初始化一个头节点,头节点不要动,不方具体的数据
        private HereNode head =new HereNode(0,"","");
        //添加节点到单向链表
        //思路当不考虑编号顺序时,
        //1.找到当前链路的节点,
        //将最后节点的next指向新的节点
        public void add(HereNode hereNode){
            //因为头节点不能动,所以我们需要一个临时temp去协助遍历
            HereNode temp=head;
            //遍历链表找到最后
            while(true){
                if (temp.next==null){
                    break;
                }
                //如果没有找到,就将temp后移到下一个节点
              temp = temp.next;
            }
            //当退出while循环时就表示,temp指向了链表的尾部
            //将最后节点的next指向新的节点
            temp.next=hereNode;
        }
        //第二种添加英雄的方法,按照排名插入
        //如果插入的排名已经存在就不能插入成功,并返回一定的提示信息
        public void addHereByOder(HereNode hereNode){
            //因为头节点不能动,所以我们需要辅助变量帮助我们遍历
            //因为是单链表所以temp指向的是要插入结点的前一个节点
            HereNode temp =hereNode;
            Boolean flag =false;//设置英雄是否存在,默认不存在
            while(true){
                if (temp.next==null){
                    //表示已经再链表的结尾
                    break;
                }
                if (temp.next.no>hereNode.no){//找到了可以插入的位置
                    break;
                }else if (temp.next.no==hereNode.no){
                    flag=true;//说明已经存在
                    break;
                }
                temp=temp.next;
            }
            if (flag){
                System.out.println("角色已存在,插入失败");
            }else{
                //插入到链表中,temp的后面
                hereNode.next=temp.next;
                temp.next=hereNode;
            }
        }
        //修改节点信息,根据编号修改,不能修改编号只能修改节点的数据
    
        public void update(HereNode newHereNode){
            if (head.next==null){
                System.out.println("链表为空");
                return;
            }
            HereNode temp = head.next;
            boolean flag =false;//表示是否找到
            while(true){
                if (temp==null){
                    //表示已经遍历完了链表
                    break;
                }
                if (temp.no==newHereNode.no){
                    //找到了
                    flag=true;
                    break;
                }
            temp =temp.next;
            }
            if (flag){
                temp.name=newHereNode.name;
                temp.nickName=newHereNode.nickName;
            }else {
                System.out.println("没有找到角色");
            }
        }
        //删除链表的某一个节点
        public void delete(int no){
            HereNode temp =head;//temp是待删除节点的上一个节点
            Boolean flag =false;//判断待删除节点是否存在
           while(true){
               if (temp.next==null){//已经到了链表的最后
                   break;
               }
               if (temp.next.no==no){
                   flag=true;
                   break;
               }
               temp=temp.next;//temp后移,这样我们才能完成循环遍历
           }
           if (flag){
               temp.next=temp.next.next;//让找到的节点指向它下一个节点的下一个节点,这样没人指向它的时候,就会被GC回收掉
               return;
           }else {
               System.out.println("不好意思,没有找到想过要被删除的节点");
           }
        }
        //查询链表集合
        public void list(){
            //判断链表是否为空
            if (head.next==null){
                System.out.println("链表没有数据无法遍历");
                return;
            }
            //不为的情况下在再遍历输出链表数据
            //因为头节点不能动,所以我们需要辅助变量来帮助我们遍历
            HereNode temp =head;
            while(true){//判断是否走到了链表的尾部
                if (temp==null){
                    break;
                }
                System.out.println(temp);
                //将temp后移 否则会陷入死循环
                temp =temp.next;
            }
        }
    }
    class HereNode {
        public int no;
        public  String name;
        public String nickName;
        public HereNode next;
    
        public HereNode(int no, String name, String nickName) {
            this.no = no;
            this.name = name;
            this.nickName = nickName;
        }
    
        @Override
        public String toString() {
            return "HereNode{" +
                    "no=" + no +
                    ", name='" + name + '\'' +
                    ", nickName='" + nickName + '\'' +
                    '}';
        }
    }
    
    class test{
        public static void main(String[] args) {
            HereNode hereNode1 = new HereNode(1, "宋江", "及时雨");
            HereNode hereNode2 = new HereNode(2, "卢俊义", "玉麒麟");
            HereNode hereNode3 = new HereNode(3, "吴用", "智多星");
            HereNode hereNode4 = new HereNode(4, "林冲", "豹子头");
    
            //加入到单向链表中
            SingleLikedList list = new SingleLikedList();
            list.add(hereNode1);
            list.add(hereNode2);
            list.add(hereNode3);
            list.add(hereNode4);
    //        list.addHereByOder(hereNode1);
    //        list.addHereByOder(hereNode4);
    //        list.addHereByOder(hereNode2);
    //        list.addHereByOder(hereNode3);
            list.list();
            //测试更新
            HereNode node = new HereNode(2, "小卢", "玉麒麟~~");
            list.update(node);
            //测试删除
            list.delete(1);
            System.out.println("删除后的节点情况");
            list.list();
    
        }
    }
    

    单链表面试题(新浪、百度、腾讯)

    1)求单链表中有效节点的个数

    public int getLength(HereNode head){
            if (head.next == null){
                return 0;
            }
            int length = 0;
            //定义一个辅助的temp 指向头节点的下一个节点,因为头节点没有有效数据
            HereNode cur =head.next;
            while(cur !=null){
                length++;
                cur=cur.next;
    
            }
            return  length;
        }
    

    获取单链表中倒数第k个节点

        //查询单链表中倒数第k个节点
        //思路:编写一个方法接收head节点,同时接收index
        //index表示倒数第index节点
        //先把链表从头到尾遍历出来,得到链表总长度getlenth()
        //得到size以后就可以遍历(size-index)个
        //如果找到了就返回节点否则就返回未找到
        public HereNode findLastIndexNode(HereNode head ,int index){
            //如果链表为空,我们就返回一个null即可
            if (head.next==null){
                return null;
            }
            //第一个遍历得到链表长度,即节点的个数
            int size = getLength(head);
            //第二次遍历,size-index就是我们要找的倒数第k个节点
            //先做index的校验
            if (index<=0||index>size){
                return null;
            }
            //定义辅助变量cur,for循环定位到倒数的index
            HereNode cur = head.next;
            for (int i = 0; i <size-index ; i++) {
                cur =cur.next;
            }
            return cur;
    
        }
    
    

    单链表的翻转
    在这里插入图片描述

          //将单链表的节点翻转形成新的单链表
        public static void reserveList(HereNode head){
            //判断,当前链表为空或者当前链表只有一个节点时不用翻转直接输出
            if(head.next==null||head.next.next==null){
                return;
            }
            //定义一个辅助的指针帮助我们去遍历原来的链表
            HereNode cur= head.next;
            HereNode next =null;//指向当前节点的下一个节点
            HereNode reverseNode = new HereNode(0,"","");
            //遍历原来的列表,并从头遍历原来的链表,将遍历出来的节点依次放入到reverseNode最前端;
            while(cur!=null){
                next=cur.next;//保存当前节点下一个节点,后面会用到
                cur.next=reverseNode.next;//将cur的下一个节点指向新的链表的最前端
                reverseNode.next=cur;
                cur=next;//让cur不断的后移
            }
            //将head。next指向reverseNode.next,从而实现了单链表的反转
            head.next=reverseNode.next;
        }
    
    

    从尾到头打印链表

    /将单向链表从尾到头打印出来         //逆序打印单链表
        public void reversePrint(HereNode head) {
            if (head.next==null){
                return;//链表空直接返回
            }
            //创建一个栈,将单向链表的数据都压入栈中
            Stack<HereNode> stack = new Stack<>();
            HereNode cur =head.next;
            while(cur!=null){
                stack.push(cur);
                cur=cur.next;
            }
            //将栈中数据弹出
            while (stack.size()>0){
                System.out.println(stack.pop());//stack栈的特点是先进后出
    
            }
        }
    
    展开全文
  • 数据结构(线性结构-链表) 定义  链表是一种由节点(Node)组成的线性数据集合,每个节点通过指针指向下一个节点。它是一种由节点组成,并能用于表示序列的数据结构。 抽象数据类型 一、数组  数组有上界和...

    数据结构(线性结构-链表)

    定义

      链表是一种由节点(Node)组成的线性数据集合,每个节点通过指针指向下一个节点。它是一种由节点组成,并能用于表示序列的数据结构。

    抽象数据类型

    一、数组

      数组有上界和下界,数组的元素在上下界内是连续的。

     

     

     

    二、单链表

      每个节点仅指向下一个节点,最后一个节点指向(NULL)。

      1.单链表删除节点

      2.单链表添加节点

     

    三、双链表

      每个节点有俩个指针P,N。P指向前一个节点,N指向下一个节点;最后一个节点指向空。

     

      1.双向链表删除节点

     

      2.双向链表添加节点

     

    四、循环链表

      每个节点指向下一个节点,最后一个节点指向第一个节点。

      时间复杂度:

      索引:O(n)

      查找:O(n)

      插入:O(1)

      删除:O(1)

    五、线性表

    操作

      1.增加

    1)逻辑结构

    2)物理结构

    3)操作实现

     

      2.删除

    1)逻辑结构

    2)物理结构

    3)操作实现

      3.修改

    1)逻辑结构

    2)物理结构

    3)操作实现

    转载于:https://www.cnblogs.com/guozepingboke/p/10749690.html

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 81,321
精华内容 32,528
关键字:

线性结构的链表