数据结构 —— java 单链表、双端链表、双向链表、无序链表、有序链表

桃扇骨 2023-06-27 06:15 25阅读 0赞

## 0、节点 ##

结点 是数据结构中的基础，是 构成复杂数据结构的基本组成单位。

public class Node {
    	public long data;
    	public Node next;		
    
    	public Node(long value) {
    		this.data = value;
    	}	
    }

## 1、链表 ##

**链表：**

通常由一连串 **节点** 组成，每个节点包含任意的实例数据（data fields）和一或两个用来指向上一个/或下一个节点的位置的链接（“links”）。

![在这里插入图片描述][20190709115234318.jpg]

上面是一个单链表的存储原理图，head为头节点，它不存放任何的数据，只是充当一个指向链表中真正存放数据的第一个节点的作用，而每个节点中都有一个 next 引用，指向下一个节点，就这样一节一节往下面记录，直到最后一个节点，其中的 next 指向 null 。

## 2、链表的种类和特点 ##

**普通链表（单链表）：**  
节点类保留下一节点的引用。链表类只保留头节点的引用，只能从头节点插入删除；

**双端链表：**  
节点类保留下一节点的引用。链表类保留头节点、尾节点的引用，可以从尾节点插入，但只能从头节点删除；

**双向链表：**  
节点类保留上一节点、下一节点的引用。链表类保留头节点、尾节点的引用，可以从尾节点插入删除；

如图所示：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70]

以上统称为 **无序链表**。

**无序链表** 最大特点就是 在头部或尾部增加 新节点。

**有序链表：**

递增，递减或者其他满足一定条件的规则，插入数据时，从头结点开始遍历每个节点，在满足规则的地方插入新节点。

## 3、普通链表、单链表（单端链表） ##

单链表 是链表中结构最简单的。一个单链表的节点(Node)分为两个部分，第一个部分(data)保存或者显示关于节点的信息，另一个部分存储下一个节点的地址。最后一个节点存储地址的部分指向空值。

*  **查找**：单向链表 只可向一个方向遍历，一般查找一个节点的时候需要从第一个节点开始每次访问下一个节点，一直访问到需要的位置。
 *  **插入**：而插入一个节点，对于单向链表，我们只提供在链表头插入，只需要将当前插入的节点设置为头节点，next指向原头节点即可。
 *  **删除**：删除一个节点，我们将该节点的上一个节点的next指向该节点的下一个节点。

查找图：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70 1]

在表头增加节点：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70 2]

删除节点：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70 3]

package test.node1;
    
    public class Node {
    
    	public long data;
    	public Node next;		
    
    	public Node(long value) {
    		this.data = value;
    	}
    	
    	//显示方法
    	public void display() {
    		System.out.print(data + " ");
    	}
    	
    }

package test.node1;
    
    
    /**
     * 单链表
     */
    public class SingleEndLinkList {
    	
    	/**头点节*/
    	private Node first;
    	
    	public SingleEndLinkList() {
    		first = null;
    	}
    	
    	/**
    	 * 插入节点
    	 * <pre>
    	 * 在头结点之后插入
    	 * </pre>
    	 */
    	public void insertFirst(long value) {
    		Node aNode = new Node(value);
    		aNode.next = first;
    		first = aNode;
    	}
    	
    	//删除头节点
    	public Node deleteFirst() {
    		Node tmp = first.next;
    		first = tmp;
    		return tmp;
    	}
    	
    	
    	//显示方法
    	public void display() {
    		Node now = first;
    		while(now != null) {
    			now.display();
    			now = now.next;
    		}
    		System.out.println();
    	}
    	
    	//查找方法
    	public Node find(long value) {
    		Node now = first;
    		while(now.data != value) {
    			if(now.next == null) {
    				return null;
    			}
    			now = now.next;
    		}
    		return now;
    	}
    	
    	//根据数值删除
    	public Node delete(long value) {
    		Node now = first;
    		Node before = first;
    		while(now.data != value) {
    			if(now.next == null) {
    				return null;
    			}
    			before = now;
    			now = now.next;
    		}
    		
    		if(now == first) {
    			first = first.next;
    		}else {
    			before.next = now.next;
    		}
    		return now;
    	}
    }

## 4、双端链表 ##

节点类保留下一节点的引用。链表类保留头节点、尾节点的引用，可以从尾节点插入，但只能从头节点删除。

package test.node2;
    
    public class Node {
    	public long data;
    	public Node next;
    
    	public Node(long data) {
    		this.data = data;
    	}
    
    	// 显示方法
    	public void display() {
    		System.out.print(data + " ");
    	}
    }

package test.node2;
    
    /**
     * 双端链表
     */
    public class DoubleEndLinkedList {
        // 头节点
        private Node first;
        //尾节点
        private Node last;
        
        public DoubleEndLinkedList() {
    		first = null;
    		last = null;
    	}
    	
    	//插入节点，在头结点之后插入
    	public void insertFirst(long value) {
    		Node aNode = new Node(value);
    		if (isEmpty()) {
    			last = aNode;
    		}
    		aNode.next = first;
    		first = aNode;
    	}
    	
    	//尾节点插入
    	public void insertLast(long value) {
    		Node aNode = new Node(value);
    		if (isEmpty()) {
    			first = aNode;
    		}
    		else {
    			last.next = aNode;
    		}
    		last = aNode;
    	}
    	
    	//删除头节点
    	public Node deleteFirst() {
    		Node tmp = first;
    		if (first.next == null) {
    			last = null;
    		}
    		first = tmp.next;
    		return tmp;
    	}
    	
    	//显示方法
    	public void display() {
    		Node now = first;
    		while(now != null) {
    			now.display();
    			now = now.next;
    		}
    		System.out.println();
    	}
    	
    	//查找方法
    	public Node find(long value) {
    		Node now = first;
    		while(now.data != value) {
    			if(now.next == null) {
    				return null;
    			}
    			now = now.next;
    		}
    		return now;
    	}
    	
    	//根据数值删除
    	public Node delete(long value) {
    		Node now = first;
    		Node before = first;
    		while(now.data != value) {
    			if(now.next == null) {
    				return null;
    			}
    			before = now;
    			now = now.next;
    		}
    		
    		if(now == first) {
    			first = first.next;
    		}
    		else {
    			before.next = now.next;
    		}
    		return now;
    	}
    	
    	//判断是否为空
    	public boolean isEmpty() {
    		return first == null;
    	}
    }

为什么不能删除尾节点？ 删除尾节点时必须知道尾节点的上个节点，但是 双端链表 只能知道下个节点，不知道上个节点，故无法删除。

## 5、双向链表 ##

节点类保留上一节点、下一节点的引用。链表类保留头节点、尾节点的引用，可以从尾节点插入删除。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70 4]

package test.node3;
    
    public class Node {
        // 数据域
        public long data;
        //指针域（保存下一个节点的引用）
        public Node next;
        //指针域（保存前一个节点的引用）
        public Node previous;
    
        public Node(long value) {
            this.data = value;
        }
    
        /**
         * 显示方法
         */
        public void display() {
            System.out.print(data + " ");
        }
    }

package test.node3;
    
    
    /**
     * 双向链表
     */
    public class DoubleByLinkedList {
        // 头结点
        private Node first;
        //尾结点
        private Node last;
    
        public DoubleByLinkedList() {
            first = null;
            last = null;
        }
    
        /**
         * 插入一个节点，在头结点后进行插入
         *
         * @param value
         */
        public void insertFirst(long value) {
            Node node = new Node(value);
            if (isEmpty()) {
                last = node;
            } else {
                first.previous = node;
            }
            node.next = first;
            first = node;
        }
    
        public void insertLast(long value) {
            Node node = new Node(value);
            if (isEmpty()) {
                first = node;
            } else {
                last.next = node;
                node.previous = last;
            }
            last = node;
        }
    
        /**
         * 删除一个结点,在头结点后进行删除
         *
         * @return
         */
        public Node deleteFirst() {
            Node tmp = first;
            if (first.next == null) {
                last = null;
            } else {
                first.next.previous = null;
            }
            first = tmp.next;
            return tmp;
        }
    
        /**
         * 删除一个结点,从尾部进行删除
         *
         * @return
         */
        public Node deleteLast() {
            if (first.next == null) {
                first = null;
            } else {
                last.previous.next = null;
            }
            last = last.previous;
            return last;
        }
    
        /**
         * 显示方法
         */
        public void display() {
            Node current = first;
            while (current != null) {
                current.display();
                current = current.next;
            }
        }
    
        /**
         * 查找方法
         *
         * @param value
         * @return
         */
        public Node find(long value) {
            Node current = first;
            while (current.data != value) {
                if (current.next == null) {
                    return null;
                }
                current = current.next;
            }
            return current;
        }
    
        public Node delete(long value) {
            Node current = first;
            while (current.data != value) {
                if (current.next == null) {
                    return null;
                }
                current = current.next;
            }
            if (current == first) {
                first = first.next;
            } else {
                current.previous.next = current.next;
            }
            return current;
        }
    
        /**
         * 判断是否为空
         *
         * @return
         */
        public boolean isEmpty() {
            return first == null;
        }
    }

## 6、有序列表 ##

前面的链表实现插入数据都是无序的，在有些应用中需要链表中的数据有序，这称为有序链表。

在有序链表中，数据是按照关键值有序排列的。一般在大多数需要使用有序数组的场合也可以使用有序链表。有序链表优于有序数组的地方是插入的速度（因为元素不需要移动），另外链表可以扩展到全部有效的使用内存，而数组只能局限于一个固定的大小中。

有序列表算法题：

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4
    输出：1->1->2->3->4->4

[https://leetcode-cn.com/problems/merge-two-sorted-lists/][https_leetcode-cn.com_problems_merge-two-sorted-lists]

**想法:**递归

我们可以如下递归地定义在两个链表里的 merge 操作（忽略边界情况，比如空链表等）：

![20200104170853154.png][]

也就是说，两个链表头部较小的一个与剩下元素的 `merge` 操作结果合并。

算法  
我们直接将以上递归过程建模，首先考虑边界情况。  
特殊的，如果 l1 或者 l2 一开始就是 null ，那么没有任何操作需要合并，所以我们只需要返回非空链表。否则，我们要判断 l1 和 l2 哪一个的头元素更小，然后递归地决定下一个添加到结果里的值。如果两个链表都是空的，那么过程终止，所以递归过程最终一定会终止。

class Solution {
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            if (l1 == null) {
                return l2;
            }
            else if (l2 == null) {
                return l1;
            }
            else if (l1.val < l2.val) {
                l1.next = mergeTwoLists(l1.next, l2);
                return l1;
            }
            else {
                l2.next = mergeTwoLists(l1, l2.next);
                return l2;
            }
    
        }
    }

**复杂度分析**

*  时间复杂度：O(n + m) 因为每次调用递归都会去掉 l1 或者 l2 的头元素（直到至少有一个链表为空），函数 mergeTwoList 中只会遍历每个元素一次。所以，时间复杂度与合并后的链表长度为线性关系。
 *  空间复杂度：O(n + m)。调用 mergeTwoLists 退出时 l1 和 l2 中每个元素都一定已经被遍历过了，所以 n + m个栈帧会消耗 O(n + m) 的空间。

[20190709115234318.jpg]: https://img-blog.csdnimg.cn/20190709115234318.jpg
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190709160003381.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20190718094216843.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20190718094224250.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20190718094235222.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20190718094309824.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg==,size_16,color_FFFFFF,t_70
[https_leetcode-cn.com_problems_merge-two-sorted-lists]: https://leetcode-cn.com/problems/merge-two-sorted-lists/
[20200104170853154.png]: https://img-blog.csdnimg.cn/20200104170853154.png