一、链表概述
链表是一种常用的数据结构,它存储一系列元素,这些元素由指向下一个元素的指针引用连接而成。链表是由节点组成的,每个节点包含一个数据元素和一个指向下一节点的指针。
二、Java中的链表
Java语言中的链表是通过节点(Node)的方式实现的,每个节点包含三个部分,即指向下一个节点的指针next、节点值value、以及一个前驱指针prev(如果是双向链表)。
三、ListNode类
Java中的链表通常是通过ListNode类来实现的。ListNode类是一个简单的类,包含一个值val和一个指向下一个节点的指针next。
public class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val = val; } ListNode(int val, ListNode next) { this.val = val; this.next = next; } }
四、链表的创建
在Java中,可以通过常规的方式来创建一个链表,首先声明一个头节点(head),然后在头节点后面逐个添加新节点。这里的新节点就是ListNode类的实例。
ListNode head = new ListNode(0); ListNode node1 = new ListNode(1); ListNode node2 = new ListNode(2); head.next = node1; node1.next = node2;
五、链表的遍历
链表的遍历是指按顺序依次访问链表中的所有节点。Java链表的遍历通常使用while循环,先访问头节点(head),然后循环访问后续节点,直到访问到null节点。
ListNode head = new ListNode(0); ListNode node1 = new ListNode(1); ListNode node2 = new ListNode(2); head.next = node1; node1.next = node2; ListNode cur = head; while(cur != null) { System.out.println(cur.val); cur = cur.next; }
六、链表的插入
链表的插入指在链表的某个位置上插入新的节点。Java中链表的插入一般有三种情况,包括在链表的头部插入节点、在链表的尾部插入节点、在链表的指定位置插入节点。
(1)在链表头插入节点
首先需要创建一个新的节点,然后将新节点的next指向原来的头节点,最后将新节点赋值给头节点。
ListNode newNode = new ListNode(val); newNode.next = head; head = newNode;
(2)在链表尾部插入节点
遍历到链表尾部,然后在尾部添加新节点。
ListNode newNode = new ListNode(val); ListNode cur = head; while (cur.next != null) { cur = cur.next; } cur.next = newNode;
(3)在链表指定位置插入节点
在Java中,链表的插入是通过改变节点的指针来完成的。使用pre节点记录待插入位置的前一节点,然后先将待插入节点的next指向pre.next,再将pre.next指向待插入节点。
ListNode newNode = new ListNode(val); ListNode pre = head; for(int i=1; i
七、链表的删除
链表的删除是指在链表中删除指定节点。Java中链表的删除分为删除头节点、删除尾节点和删除中间节点。删除链表节点时需要分别进行内存释放处理,以避免造成内存泄漏。
(1)删除头节点
将头节点指针移向下一节点。
head = head.next;
(2)删除尾节点
找到尾节点的前一节点pre,将pre.next置为null,然后释放掉尾节点。
ListNode cur = head; while (cur.next.next != null) { cur = cur.next; } ListNode delNode = cur.next; cur.next = null; delNode = null;
(3)删除中间节点
找到待删除节点的前一节点pre,先将pre.next指向待删除节点的下一节点,再释放掉待删除节点。
ListNode pre = head; for(int i=1; i