常见的链表——单向链表&双向链表&循环链表

た入场券 2022-09-14 09:49 375阅读 0赞

**目录**

目标

结构图

单向链表的数据结构示意图

双向链表的数据结构示意图

循环单向链表的数据结构示意图

代码实现

单向链表

双向链表

单向循环链表

附加题

约瑟夫环

总结

--------------------

# 目标 #

*  熟悉单向链表、双向链表、单向循环链表的数据结构，包括增删改查操作；
 *  用代码实现这三种链表结构。

--------------------

# 结构图 #

## 单向链表的数据结构示意图 ##

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bGx5YmN55WZ5ZCN_size_20_color_FFFFFF_t_70_g_se_x_16][]

## 双向链表的数据结构示意图 ##

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bGx5YmN55WZ5ZCN_size_20_color_FFFFFF_t_70_g_se_x_16 1][]

## 循环单向链表的数据结构示意图 ##

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bGx5YmN55WZ5ZCN_size_20_color_FFFFFF_t_70_g_se_x_16 2][]

--------------------

# 代码实现 #

## 单向链表 ##

package com.ctx;
    
    import java.util.NoSuchElementException;
    
    /**
     * 实现单向链表
     */
    public class UnidirectionalLinkedList<T> {
        //集合的大小
        private int size = 0;
        //集合的第一个元素
        private Node<T> pred;
        //集合的最后一个元素
        private Node<T> last;
    
        /**
         * 元素类
         */
        private static class Node<T> {
            T item;
            Node<T> next;
    
            Node(T item, Node<T> next) {
                this.item = item;
                this.next = next;
            }
        }
    
        public static void main(String[] args) {
            UnidirectionalLinkedList<String> list = new UnidirectionalLinkedList();
            list.add(0,"a");
            list.add(1,"b");
            list.add(2,"c");
            list.removeLast();
            list.removeFirst();
            //遍历集合
            Node node = list.pred;
            while (node != null) {
                System.out.println(node.item);
                node = node.next;
            }
            System.out.println(list.size());
        }
    
        /**
         * 集合的元素个数
         *
         * @return
         */
        public int size() {
            return size;
        }
    
        /**
         * 增加元素到头部
         */
        private boolean addPred(T t) {
            Node<T> newNode = new Node<T>(t, null);
            if (size == 0) {
                pred = newNode;
                last = newNode;
            } else {
                Node<T> tempNode = pred;
                pred = newNode;
                pred.next = tempNode;
            }
            size++;
            return true;
        }
    
        /**
         * 增加元素到尾部
         */
        public boolean add(T t) {
            Node<T> newNode = new Node<T>(t, null);
            if (size == 0) {
                pred = newNode;
            } else {
                last.next = newNode;
            }
            last = newNode;
            size++;
            return true;
        }
    
        /**
         * 增加元素到指定位置
         */
        public boolean add(int index, T t) {
            //如果下标正好在集合的最后一个元素的下一个空间，则相当于直接在尾部添加元素。
            if (index == size) {
                return add(t);
            } else if (index == 0) {//相当于元素插入集合的头部
                addPred(t);
                return true;
            }
            Node<T> tempNode = pred;
            //已经确定了要插入的位置不是第一个，所以循环从1开始。
            for (int i = 1; i < index; i++) {
                //获取下标为index的元素。
                tempNode = tempNode.next;
            }
            //新元素顶替了原来的元素的位置。
            Node<T> newNode = new Node<T>(t, tempNode.next);
            tempNode.next = newNode;
            size++;
            return true;
        }
    
        /**
         * 移除头部元素
         *
         * @return
         */
        public T removeFirst() {
            Node<T> f = pred;
            if (f == null) {
                throw new NoSuchElementException();
            }
            T t = f.item;
            Node<T> next = f.next;
            pred = next;
            if (next == null) {
                last = null;
            }
            size--;
            return t;
        }
    
        /**
         * 移除尾部元素
         *
         * @return
         */
        public T removeLast() {
            Node<T> l = last;
            if (l == null) {
                throw new NoSuchElementException();
            }
            T t = last.item;
            size--;
            if(size==0){
                pred=null;
                last=null;
            }else{
                last =getNode(size-1);
                last.next=null;
            }
            return t;
        }
    
        public T remove(int index) {
            if (size == 0 || size < index + 1) {
                throw new IndexOutOfBoundsException();
            }
            if (index == 0) {
                return removeFirst();
            }
            if (index + 1 == size) {
                return removeLast();
            }
            Node tempNode = pred;
            for (int i = 1; i < index; i++) {
                tempNode = tempNode.next;
            }
            Node<T> node = tempNode.next;
            T t = node.item;
            tempNode.next = tempNode.next.next;
            size--;
            return t;
        }
    
        /**
         * 根据下标查询数据
         *
         * @param index
         * @return
         */
        public T get(int index) {
            if (size < index + 1) {
                throw new IndexOutOfBoundsException();
            }
            //从头部开始遍历。
            Node<T> tempNode = pred;
            for (int i = 0; i <= index; i++) {
                if (i == 0) {
                    tempNode = pred;
                } else {
                    tempNode = tempNode.next;
                }
            }
            return tempNode.item;
        }
    
        /**
         * 根据下标查询节点
         *
         * @param index
         * @return
         */
        public Node<T> getNode(int index) {
            if (size < index + 1) {
                throw new IndexOutOfBoundsException();
            }
            //从头部开始遍历。
            Node<T> tempNode = pred;
            for (int i = 0; i <= index; i++) {
                if (i == 0) {
                    tempNode = pred;
                } else {
                    tempNode = tempNode.next;
                }
            }
            return tempNode;
        }
    }

## 双向链表 ##

package com.ctx;
    
    import com.sun.scenario.effect.impl.sw.sse.SSEBlend_SRC_OUTPeer;
    
    import java.util.NoSuchElementException;
    
    /**
     * 实现双向链表
     */
    public class BidirectionalLinkedList<T> {
        //集合的大小
        private int size = 0;
        //集合的第一个元素
        private Node<T> pred;
        //集合的最后一个元素
        private Node<T> last;
    
        /**
         * 元素类
         */
        private static class Node<T> {
            T item;
            //下一个元素
            Node<T> next;
            //上一个元素
            Node<T> prev;
            Node(T item,Node<T> prev, Node<T> next) {
                this.item = item;
                this.next = next;
                this.prev=prev;
            }
        }
    
        public static void main(String[] args) {
            BidirectionalLinkedList<String> list = new BidirectionalLinkedList();
            list.add(0,"a");
            list.add(1,"b");
            list.add(2,"c");
            list.removeLast();
            list.removeFirst();
            //遍历集合
           Node node = list.pred;
            while (node != null) {
                System.out.println(node.item);
                node = node.next;
            }
            System.out.println("=======================");
            Node node2 = list.last;
            while (node2 != null) {
                System.out.println(node2.item);
                node2 = node2.prev;
            }
        }
    
        /**
         * 集合的元素个数
         *
         * @return
         */
        public int size() {
            return size;
        }
    
        /**
         * 增加元素到头部
         */
        private boolean addPred(T t) {
            Node<T> newNode = new Node<T>(t, null,null);
            if (size == 0) {
                pred = newNode;
                last = newNode;
            } else {
                Node<T> tempNode = pred;
                pred = newNode;
                pred.next = tempNode;
            }
            size++;
            return true;
        }
    
        /**
         * 增加元素到尾部
         */
        public boolean add(T t) {
            Node<T> newNode = new Node<T>(t, null,null);
            if (size == 0) {
                pred = newNode;
            } else {
                last.next = newNode;
                newNode.prev=last;
            }
            last = newNode;
            size++;
            return true;
        }
    
        /**
         * 增加元素到指定位置
         */
        public boolean add(int index, T t) {
            //如果下标正好在集合的最后一个元素的下一个空间，则相当于直接在尾部添加元素。
            if (index == size) {
                return add(t);
            } else if (index == 0) {//相当于元素插入集合的头部
                addPred(t);
                return true;
            }
            Node<T> tempNode = pred;
            //已经确定了要插入的位置不是第一个，所以循环从1开始。
            for (int i = 1; i < index; i++) {
                //获取下标为index的元素。
                tempNode = tempNode.next;
            }
            //新元素顶替了原来的元素的位置。
            Node<T> newNode = new Node<T>(t, tempNode,tempNode.next);
            tempNode.next = newNode;
            size++;
            return true;
        }
    
        /**
         * 移除头部元素
         *
         * @return
         */
        public T removeFirst() {
            Node<T> f = pred;
            if (f == null) {
                throw new NoSuchElementException();
            }
            T t = f.item;
            Node<T> next = f.next;
            pred = next;
            if (next == null) {
                last = null;
            }else{
                next.prev=null;
            }
            size--;
            return t;
        }
    
        /**
         * 移除尾部元素
         * @return
         */
        public T removeLast() {
            Node<T> l = last;
            if (l == null) {
                throw new NoSuchElementException();
            }
            T t = last.item;
            Node<T> node = last.prev;
            size--;
            if(size==0){
                pred=null;
                last=null;
            }else{
                last=node;
                node.next=null;
            }
            return t;
        }
    
        public T remove(int index) {
            if (size == 0 || size < index + 1) {
                throw new IndexOutOfBoundsException();
            }
            if (index == 0) {
                return removeFirst();
            }
            if (index + 1 == size) {
                return removeLast();
            }
            Node tempNode = pred;
            for (int i = 1; i < index; i++) {
                tempNode = tempNode.next;
            }
            Node<T> node = tempNode.next;
            T t = node.item;
            tempNode.next = tempNode.next.next;
            size--;
            return t;
        }
    
        /**
         * 根据下标查询数据
         *
         * @param index
         * @return
         */
        public T get(int index) {
            if (size < index + 1) {
                throw new IndexOutOfBoundsException();
            }
            //从头部开始遍历。
            Node<T> tempNode = pred;
            for (int i = 0; i <= index; i++) {
                if (i == 0) {
                    tempNode = pred;
                } else {
                    tempNode = tempNode.next;
                }
            }
            return tempNode.item;
        }
    
    }

## 单向循环链表 ##

package com.ctx;
    
    import java.util.NoSuchElementException;
    
    /**
     * 实现单向循环链表
     */
    public class CircularLinkedList<T> {
        //集合的大小
        private int size = 0;
        //集合的第一个元素
        public Node<T> pred;
        //集合的最后一个元素
        public Node<T> last;
    
        /**
         * 元素类
         */
        public static class Node<T> {
            T item;
            Node<T> next;
            Node(T item, Node<T> next) {
                this.item = item;
                this.next = next;
            }
            Node(){
    
            }
        }
    
    
        public static void main(String[] args) {
            CircularLinkedList<String> list = new CircularLinkedList();
    
            list.add("a");
            list.add("b");
            list.add("c");
            list.add("d");
            list.add("e");
    
            System.out.println(list.findIndex(list,"d"));
            list.remove(3);
            System.out.println(list.size());
            for (int i = 0; i < list.size(); i++) {
                System.out.println(list.get(i));
            }
            //遍历集合
           /* Node node = list.pred;
            while (node != null) {
                System.out.println(node.item);
                node = node.next;
            }*/
    
        }
    
        /**
         * 集合的元素个数
         *
         * @return
         */
        public int size() {
            return size;
        }
    
        /**
         * 增加元素到头部
         */
        private boolean addPred(T t) {
            Node<T> newNode = null;
            if (size == 0) {
                pred=new Node<T>();
                last=new Node<T>();
                pred.next=last;
                pred.item=t;
                last.next=pred;
                last.item=t;
                size++;
                return true;
            } else {
                newNode=new Node<T>();
                newNode.item=t;
                newNode.next=pred;
                //更换头节点
                pred = newNode;
                last.next=newNode;
                if(size==1){
                    pred.next=last;
                }
            }
            size++;
            return true;
        }
    
        /**
         * 增加元素到尾部
         */
        public boolean add(T t) {
            Node<T> newNode = null;
            if (size == 0) {
                addPred(t);
                return true;
            } else {
                newNode=new Node<T>();
                newNode.item=t;
                if(size==1){
                    pred.next=newNode;
                }
                newNode.next=pred;
                last.next = newNode;
                last = newNode;
            }
            size++;
            return true;
        }
    
        /**
         * 增加元素到指定位置
         */
        public boolean add(int index, T t) {
            if(index>size){
                throw new IndexOutOfBoundsException();
            }
            //新元素增加到头部和增加到尾部是一样的逻辑。
            if (index == size) {
                return add(t);
            }else if(index == 0){
                return addPred(t);
            }
            Node<T> tempNode = pred;
            //已经确定了要插入的位置不是第一个，所以循环从1开始。
            for (int i = 1; i < index; i++) {
                //获取下标为index的元素。
                tempNode = tempNode.next;
            }
            //新元素顶替了原来的元素的位置。
            Node<T> newNode = new Node<T>(t, tempNode.next);
            tempNode.next = newNode;
            size++;
            return true;
        }
    
        /**
         * 移除头部元素
         *
         * @return
         */
        public T removeFirst() {
            Node<T> f = pred;
            if (f == null) {
                throw new NoSuchElementException();
            }
            Node<T> next = f.next;
            pred = next;
            if (next == null) {
                last = null;
            }else{
                last.next=pred;
            }
            size--;
            return f.item;
        }
    
        /**
         * 移除尾部元素
         *
         * @return
         */
        public T removeLast() {
            Node<T> l = last;
            if (l == null) {
                throw new NoSuchElementException();
            }
            size--;
            if(size==0){
                pred=null;
                last=null;
            }else{
                last =getNode(size-1);
                last.next=pred;
            }
            return last.item;
        }
    
        public T remove(int index) {
            if (size == 0 || size < index + 1) {
                throw new IndexOutOfBoundsException();
            }
            if (index == 0) {
                return removeFirst();
            }
            if (index + 1 == size) {
                return removeLast();
            }
            Node tempNode = pred;
            for (int i = 1; i < index; i++) {
                tempNode = tempNode.next;
            }
            Node<T> node = tempNode.next;
            tempNode.next = tempNode.next.next;
            size--;
            return node.item;
        }
    
        /**
         * 根据下标查询数据
         *
         * @param index
         * @return
         */
        public T get(int index) {
            if (size < index + 1) {
                throw new IndexOutOfBoundsException();
            }
            //从头部开始遍历。
            Node<T> tempNode = pred;
            for (int i = 0; i <= index; i++) {
                if (i == 0) {
                    tempNode = pred;
                } else {
                    tempNode = tempNode.next;
                }
            }
            return tempNode.item;
        }
    
        /**
         * 根据下标查询节点
         *
         * @param index
         * @return
         */
        public Node<T> getNode(int index) {
            if (size < index + 1) {
                throw new IndexOutOfBoundsException();
            }
            //从头部开始遍历。
            Node<T> tempNode = pred;
            for (int i = 0; i <= index; i++) {
                if (i == 0) {
                    tempNode = pred;
                } else {
                    tempNode = tempNode.next;
                }
            }
            return tempNode;
        }
    
        /**
         * 查询链表里面元素的下标
         * @param list
         * @param t
         * @return
         */
        public int findIndex(CircularLinkedList<T> list,T t){
            //遍历集合
            for (int i = 0; i < list.size(); i++) {
                if(list.get(i).equals(t)){
                    return i;
                }
            }
            return -1;
        }
    }

# 附加题 #

## 约瑟夫环 ##

package com.ctx;
    
    /**
     * 约瑟夫淘汰问题（类似于丢手绢问题）：
     * 有n（n是常数）个人围成一圈，从第一个人开始报数，报到m的人淘汰出圈。剩下的人继续报数，直到剩下最后一人。
     * <p>
     * 举例：
     * n=5，m=6，则剩下的人依次是：
     * 2,3,4,5
     * 2,4,5
     * 4,5
     * 4
     * <p>
     * 分析：
     * 每次淘汰一人后仍然循环报数（n>1），因此可以用单向循环链表解决该问题。
     */
    public class YSF {
        /**
         * @param n 人数
         * @param m 报数
         * @return 人员标号（从1开始）
         */
        public static int fun(Integer n, int m) {
            CircularLinkedList<Integer> list = new CircularLinkedList<Integer>();
            for (int i = 1; i <= n; i++) {
                list.add(i);
            }
            CircularLinkedList.Node node = list.pred;
            for (int j = 1; list.size() > 1; j++) {
                //遍历集合
                System.out.println("第" + node.item + "个人报数：" + j);
                CircularLinkedList.Node tempNode=node.next;
                if(j==m&&list.size() > 1){
                    int no=Integer.parseInt(node.item.toString());
                    System.out.println("淘汰："+no);
                    int index = list.findIndex(list, no );
                    list.remove(index);
                    System.out.println("剩余人数："+list.size());
                    j=0;
                }
                node = tempNode;
            }
            return list.get(0);
        }
    
        public static void main(String[] args) {
            System.out.println(YSF.fun(5, 6));
        }
    }

--------------------

# 总结 #

1.  链表的插入元素时间复杂度是O(1)；
2.  链表的随机访问时间复杂度是O(n)；
3.  链表支持动态扩容；
4.  链表中的元素的节点包括数据和引用，引用指向的是节点而非数据。

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bGx5YmN55WZ5ZCN_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/904d1c2e3da44a5c9e00c88e5df9c97f.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bGx5YmN55WZ5ZCN_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/043f6f37c45348d4b74a9a224b4d6469.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bGx5YmN55WZ5ZCN_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/f866a117c4dd42f384ece792a527c0c3.png