赞
踩
节点 是数据结构中的基础,是 构成复杂数据结构的基本组成单位。
public class Node {
public long data;
public Node next;
public Node(long value) {
this.data = value;
}
}
链表:
通常由一连串 节点 组成,每个节点包含任意的实例数据(data fields)和一或两个用来指向 上一个 或 下一个 节点的位置的链接(“links”)。
上面是一个单链表的存储原理图,head为头节点,它不存放任何的数据,只是充当一个指向链表中真正存放数据的第一个节点的作用,而每个节点中都有一个 next 引用,指向下一个节点,就这样一节一节往下面记录,直到最后一个节点,其中的 next 指向 null 。
(1)普通链表(单链表):
单链表的节点类
保留下一节点的引用。链表类
只保留头节点的引用,只能从头节点插入删除 (思考为什么?);
(2)双端链表:
双端链表的节点类
保留下一节点的引用。链表类
保留头节点、尾节点的引用,可以从尾节点插入,但只能从头节点删除 (思考为什么?);
(3)双向链表:
双向链表的节点类
保留上一节点、下一节点的引用。链表类
保留头节点、尾节点的引用,可以从尾节点插入删除;
如图所示:
(4)无序链表 最大特点就是 在头部或尾部增加 新节点。
上面几种 链表都是 无序链表。
(5)有序链表:
递增,递减或者其他满足一定条件的规则,插入数据时,从头结点开始遍历每个节点,在满足规则的地方插入新节点。
普通链表 ,也叫 单链表 或者 单向链表。
链表是一种数据存储结构。在Java原生JDK中对于链表也进行了相应实现。 单向链表是链表的其中一种,其主要原理是:
链表是以节点(Node)的形式存储数据,节点对象中存储了要保存的数据。
单向链表中的每一个节点中都持有下一个节点的引用(Node next),通过上一个节点就可以找到下一个节点,依次串联,所以想要遍历整个单向链表就需要找到第一个节点。
**链表不同于数组,在内存中不一定是连续的空间,**由于是节点存储,可以利用内存中零散的空间进行保存,只需持有下一个节点的地址即可。
很多人都知道链表相较于List他增删快,查询慢,主要因为,链表的修改只需要将前一个节点和后一个节点中所持的前后节点的引用进行修改,而list在进行删除或者增加操作时,往往需要将集合中的元素进行移动,所以较为耗费时间较长,但是,实际上还是需要根据实际情况来判断,如果不考虑随机插入的情况,一直是在最后进行插入,list是非常快的,因为不需要进行元素的移动,但如果是随机插入或者是在靠前的位置进行插入,链表则有很大的优势,所以到底谁快谁慢还是要结合具体问题.
单链表 是链表中结构最简单的。一个单链表的节点(Node)分为两个部分,第一个部分(data)保存或者显示关于节点的信息,另一个部分存储下一个节点的地址。最后一个节点存储地址的部分指向空值。
查找图:
在表头增加节点:
删除节点:
在JDK中已经封装好了链表的集合容器,我们直接用就行了,但是手动的实现一些基本功能还是有助于更好的了解底层的原理加深对于这种数据结构的认识。
/*** * 节点 */ class Node{ //************数据层************ //可封装为Object public int no; public String name ; public String nick; //****************************** //下一个节点的引用 public Node next; public Node(int no , String name , String nick){ this.no = no ; this.name = name ; this.nick = nick ; } @Override public String toString() { return "Node{" + "no=" + no + ", name='" + name + '\'' + ", nick='" + nick + '\'' + '}'; } }
首先我们需要声明一个头结点Head,这个head不存放具体的数据,只是记录第一个节点的地址。
public class LinkedList {
//声明一个头结点.这个节点不放具体的数据,只记录第一个节点的地址
//根据上面的Node的构造方法初始化,next指针先不赋值.
private Node head = new Node(0 , "" , "");
}
public class LinkedList { //声明一个头结点.这个节点不放具体的数据,只记录第一个节点的地址 private Node head = new Node(0 , "" , ""); /** * 添加方法,这里的添加需要保证插入的Node是新的next是null,如果next的值不为空之前使用过指向另一个 * Node地址的话会出现添加一个却把之前链表都连起来的情况,如果恰巧形成了闭环,首尾相连会出现死循环的情况 * @param newNode * @return */ public boolean add(Node newNode){ //声明一个第三变量用作指针,开始默认指向头结点 Node temp = head; //循环遍历链表,将新节点加入到next为null的节点后,就是直接加入到最后一个节点的后面 while(true){ //如果当前节点的下一个节点是null ,说明该节点是最后一个节点 if(temp.next == null){ //直接将新节点添加到最后一个节点之后,next指向新节点 temp.next = newNode; return true; } //将指针后移一位,指针指向下一个节点 temp = temp.next ; } } }
/**
* 判断链表是否为空的方法
* @return
*/
public boolean isEmpty(){
//如果头结点的下一个是空,就说明链表是空的
return head.next == null ;
}
public boolean update(Node newNode) { //首先需要找到要修改的节点 Node temp = head; //如果为空直接返回 if(isEmpty()){ System.out.println("链表为空"); return false; } //遍历链表 /* 如果当前节点的下一个节点的no值和要修改的节点的no值相同,说明当前节点的下一个节点就是要修改的 节点,此时的temp指针指向的是要修改节点的前一个节点,只需要将前一个节点的next指向新的节点,然后 将新的节点的next指向原来要修改的节点的next,就是将要修改的节点的next值赋给新的节点 */ while(temp.next != null){ //如果找到了相同的no值说明找到了要修改的节点 if(temp.next.no == newNode.no){ /* 首先将要修改节点的next值赋给新节点 , 此时temp.next指向的是要修改的节点,所以要修改节点的 next的值是temp.next.next */ newNode.next = temp.next.next; //然后将当前节点的next指向新的节点 temp.next = newNode; return true; } //指针后移 temp = temp.next; } System.out.println("没有找到该节点"); return false; }
/** * 删除方法,根据no值来删除 * 该方法与之前修改方法类似,只需将要删除节点的的上一个next直接指向要删除节点的next * @return */ public boolean del(int no){ //第三变量默认指向头结点 Node temp = head; if(isEmpty()){ System.out.println("链表为空"); return false; } while(temp.next != null){ //如果找到了要删除的节点 if(temp.next.no == no){ //就将当前节点的next指向要删除的的next //注意此时的temp指向的是要删除节点的前一个 temp.next = temp.next.next; return true ; } //指针后移 temp = temp.next; } System.out.println("没找到要删除的节点"); return false; }
/**
* 遍历方法
*/
public void showList(){
Node temp = head;
if (isEmpty()){
System.out.println("链表为空");
}
while(temp.next != null){
System.out.println(temp.next);
temp = temp.next;
}
}
/**
* 统计头结点的个数,不包含头结点
*/
public int size(){
int size = 0 ;
Node temp = head.next;
while(temp != null){
size++;
temp = temp.next;
}
return size;
}
综合代码
public class LinkedList { //声明一个头结点.这个节点不放具体的数据,只记录第一个节点的地址 private Node head = new Node(0 , "" , ""); /** * 添加方法,这里的添加需要保证插入的Node是新的next是null,如果next的值不为空之前使用过指向另一个 * Node地址的话会出现添加一个却把之前链表都连起来的情况,如果恰巧形成了闭环,首尾相连会出现死循环的情况 * @param newNode * @return */ public boolean add(Node newNode){ //声明一个第三变量用作指针,开始默认指向头结点 Node temp = head; //循环遍历链表,将新节点加入到next为null的节点后,就是直接加入到最后一个节点的后面 while(true){ //如果当前节点的下一个节点是null ,说明该节点是最后一个节点 if(temp.next == null){ //直接将新节点添加到最后一个节点之后,next指向新节点 temp.next = newNode; return true; } //将指针后移一位,指针指向下一个节点 temp = temp.next ; } } /** * 判断链表是否为空的方法 * @return */ public boolean isEmpty(){ //如果头结点的下一个是空,就说明链表是空的 return head.next == null ; } /** * 修改链表中数据的方法 * 需要提供一个新的节点,根据新节点的id值找到原来的节点,将原数据进行修改,id值不变 * @return */ public boolean update(Node newNode) { //首先需要找到要修改的节点 Node temp = head; //如果为空直接返回 if(isEmpty()){ System.out.println("链表为空"); return false; } //遍历链表 /* 如果当前节点的下一个节点的no值和要修改的节点的no值相同,说明当前节点的下一个节点就是要修改的 节点,此时的temp指针指向的是要修改节点的前一个节点,只需要将前一个节点的next指向新的节点,然后 将新的节点的next指向原来要修改的节点的next,就是将要修改的节点的next值赋给新的节点 */ while(temp.next != null){ //如果找到了相同的no值说明找到了要修改的节点 if(temp.next.no == newNode.no){ /* 首先将要修改节点的next值赋给新节点 , 此时temp.next指向的是要修改的节点,所以要修改节点的 next的值是temp.next.next */ newNode.next = temp.next.next; //然后将当前节点的next指向新的节点 temp.next = newNode; return true; } //指针后移 temp = temp.next; } System.out.println("没有找到该节点"); return false; } /** * 遍历方法 */ public void showList(){ Node temp = head; if (isEmpty()){ System.out.println("链表为空"); } while(temp.next != null){ System.out.println(temp.next); temp = temp.next; } } /** * 删除方法,根据no值来删除 * 该方法与之前修改方法类似,只需将要删除节点的的上一个next直接指向要删除节点的next * @return */ public boolean del(int no){ //第三变量默认指向头结点 Node temp = head; if(isEmpty()){ System.out.println("链表为空"); return false; } while(temp.next != null){ //如果找到了要删除的节点 if(temp.next.no == no){ //就将当前节点的next指向要删除的的next //注意此时的temp指向的是要删除节点的前一个 temp.next = temp.next.next; return true ; } //指针后移 temp = temp.next; } System.out.println("没找到要删除的节点"); return false; } /** * 统计头结点的个数,不包含头结点 */ public int size(){ int size = 0 ; Node temp = head.next; while(temp != null){ size++; temp = temp.next; } return size; } } /*** * 节点 */ class Node{ //************数据层************ public int no; public String name ; public String nick; //****************************** public Node next; public Node(int no , String name , String nick){ this.no = no ; this.name = name ; this.nick = nick ; } @Override public String toString() { return "Node{" + "no=" + no + ", name='" + name + '\'' + ", nick='" + nick + '\'' + '}'; } }
public class Test { public static void main(String[] args) { LinkedList linkedList = new LinkedList(); Node n1 = new Node(1 , "宋江" , "及时雨"); Node n2 = new Node(2 , "卢俊义" , "玉麒麟"); Node n3 = new Node(3 , "吴用" , "智多星"); Node n4 = new Node(4 , "李逵" , "黑旋风"); Node n5 = new Node(5 , "林冲" , "豹子头"); linkedList.addByOrder(n1); linkedList.addByOrder(n3); linkedList.addByOrder(n2); linkedList.addByOrder(n5); linkedList.addByOrder(n4); System.out.println("修改之后~~~~~~~"); Node n6 = new Node(5 , "冲冲" , "豹子头~~~"); linkedList.update(n6); linkedList.showList(); System.out.println("移除之后~~~~~~~"); linkedList.del(5); linkedList.del(1); linkedList.del(2); linkedList.del(3); linkedList.del(4); linkedList.showList(); //之前的节点不能使用,需要新建节点,保证next值为null Node n11 = new Node(1 , "宋江" , "及时雨"); Node n7 = new Node(2 , "卢俊义" , "玉麒麟"); Node n8 = new Node(3 , "吴用" , "智多星"); Node n9 = new Node(4 , "李逵" , "黑旋风"); Node n10 = new Node(5 , "林冲" , "豹子头"); System.out.println("添加之后~~~~~~~"); linkedList.add(n11); linkedList.add(n7); linkedList.add(n8); linkedList.add(n9); linkedList.add(n10); linkedList.showList();
双端链表的节点类保留下一节点的引用。(单向引用)
双端链表: 保留对头节点、尾节点的引用,可以从尾节点插入,但只能从头节点删除,只能从一个方向遍历,相当于单向链表多了一个对尾节点的引用。
双端链表的特点:
双端链表的含有对 第一个节点 和 最后一个节点的引用 。
|
双端链表的操作 | 读取(引用) | 插入 | 删除 |
---|---|---|---|
头部 | √ | √ | √ |
尾部 | √ | √ | x |
双端链表: 只能从一个方向遍历,相当于 单向链表 多了一个对尾节点的引用。
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; } }
为什么不能删除尾节点? 删除尾节点时必须知道尾节点的上个节点,但是 双端链表 只能知道下个节点,不知道上个节点,故无法删除。
双向链表 的节点类保留上一节点、下一节点的引用。
双向链表 保留头节点、尾节点的引用,可以从尾节点插入删除。
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; } }
前面的链表实现插入数据都是无序的,在有些应用中需要链表中的数据有序,这称为有序链表。
在有序链表中,数据是按照关键值有序排列的。一般在大多数需要使用有序数组的场合也可以使用有序链表。有序链表优于有序数组的地方是插入的速度(因为元素不需要移动),另外链表可以扩展到全部有效的使用内存,而数组只能局限于一个固定的大小中。
有序列表算法题:
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例:
输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4
12
参考链接:
https://leetcode-cn.com/problems/merge-two-sorted-lists/
https://www.cnblogs.com/ysocean/p/7928988.html#_label0
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。