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

本是古典何须时尚 2021-12-11 14:59 355阅读 0赞

### 文章目录 ###

*   *  0、节点
     *  1、链表的定义
     *  2、链表的种类和特点
     *  3、普通链表、单链表（单向链表）
     *  4、双端链表（单向引用）
     *  5、双向链表
     *  6、有序列表

## 0、节点 ##

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

![在这里插入图片描述][20210312114019958.png]

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

## 1、链表的定义 ##

**链表：**

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

![在这里插入图片描述][20210312114147315.png]

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

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

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

**（2）双端链表：**  
双端链表的节点类保留下一节点的引用。链表类保留头节点、尾节点的引用，可以从尾节点插入，但只能从头节点删除 *（思考为什么？）*；

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

如图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70]

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

上面几种 链表都是 **无序链表**。

**（5）有序链表：**

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

## 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 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 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、双端链表（单向引用） ##

双端链表的节点类保留下一节点的引用。（单向引用）

**双端链表：** 保留对头节点、尾节点的引用，可以从尾节点插入，但只能从头节点删除，只能从一个方向遍历，相当于单向链表多了一个对尾节点的引用。

**双端链表的特点：**  
双端链表的含有对 第一个节点 和 最后一个节点的引用 。

<table> 
 <thead> 
  <tr> 
   <th>双端链表的操作</th> 
   <th>读取（引用）</th> 
   <th>插入</th> 
   <th>删除</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>头部</td> 
   <td>√</td> 
   <td>√</td> 
   <td>√</td> 
  </tr> 
  <tr> 
   <td>尾部</td> 
   <td>√</td> 
   <td>√</td> 
   <td>x</td> 
  </tr> 
 </tbody> 
</table>

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

**双端链表：** 只能从一个方向遍历，相当于 单向链表 多了一个对尾节点的引用。  
![在这里插入图片描述][20200802165718324.png]

package 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 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 5]

package 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 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/

[20210312114019958.png]: /images/20211211/6717cba0a18a4dffb9c87dfc062edcbc.png
[20210312114147315.png]: /images/20211211/1fe5aeae266643699e63bde7ce8f036f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70]: /images/20211211/0f03ece4568c417280373ff52faaed7b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70 1]: /images/20211211/2af04ee43d1d4befa71f3decfe3ea82a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70 2]: /images/20211211/96afb7ad3d6c42e99aec90a4c4653373.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70 3]: /images/20211211/e3e7eb44fad44bf4acc0732db13487c8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70 4]: /images/20211211/9def962497ef45a8a6419fbed637fb6e.png
[20200802165718324.png]: /images/20211211/1f7000ab6ad442d1b745fd2c54be3f80.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9qaW4yMWNlbg_size_16_color_FFFFFF_t_70 5]: /images/20211211/ccd2d7940e0548cca4ae57627db394be.png