链表的原理
image.png
元素(element)：真实存于线性表中的内容，是我们关心得核心内容。
结点(node): 为了组织链表而引入的一个结构，除了保存我们的元素之外，还会保存指向下一个结点的引用。
class Node {
int val; //保存元素
Node next; //指向下一个结点的引用，其中尾结点用 next = null 表示
链表(linked list):：最终的线性表，表示逻辑上的 [1, 2, 3, 4]
目前，我们通过链表的头结点，来代表一整条链表
Node head = ...; //用头结点来代表某个链表
Node head = null; //该链表是空链表
image.png
当前结点(current / cur): 表示链表中某个结点。
前驱结点(previous / prev): 表示链表中某个结点的前一个结点；头结点没有前驱结点。
后继结点(next): 表示链表中某个结点的后一个结点；尾结点没有后继结点。
链表的结点定义
public class Node {
int val;
Node next;
public Node(int val) {
this.val = val;
this.next = null;
}
@Override
public String toString() {
return "Node{" + val + "}";
}
}
链表的手工创建
创建一个 [1, 2, 3, 6] 的链表
public class Node {
int val;
Node next;
public Node(int val) {
this.val = val;
this.next = null;
}
@Override
public String toString() {
return "Node{" + val + "}";
}
public static void main(String[] args) {
Node n1 = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
Node n4 = new Node(6);
n1.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = null;
Node head = n1;
}
}
创建一个空链表
Node head = null;
链表的遍历
public class Node {
int val;
Node next;
public Node(int val) {
this.val = val;
this.next = null;
}
@Override
public String toString() {
return "Node{" + val + "}";
}
public static void main(String[] args) {
Node n1 = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
Node n4 = new Node(6);
n1.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = null;
Node head = n1;
Node cur = head;
while(cur != null) {
System.out.println(cur);
cur = cur.next;
}
}
}
image.png
链表元素的插入和删除
public class LinkedList {
private ListNode head = null;
// 删除所有等于指定值的结点
public void removeAll(int toRemove) {
ListNode dummyNode = new ListNode(-1);
ListNode tailNode = dummyNode;
for (ListNode curNode = this.head; curNode != null; curNode = curNode.next) {
if (curNode.val != toRemove) {
tailNode.next = curNode;
tailNode = curNode;
}
}
tailNode.next = null;
this.head = dummyNode.next;
}
// 删除指定结点
public void remove(int toRemove) {
if (this.head == null) {
return;
}
if (this.head.val == toRemove) {
this.head = this.head.next;
return;
}
for (ListNode curNode = this.head; curNode.next != null; curNode = curNode.next) {
if (curNode.next.val == toRemove) {
curNode.next = curNode.next.next;
return;
}
}
}
// 是否包含
public boolean contains(int target) {
for (ListNode curNode = this.head; curNode != null; curNode = curNode.next) {
if (curNode.val == target) {
return true;
}
}
return false;
}
// 插入到指定下标
public void addIndex(int index, int val) {
int size = this.size();
if (index < 0 || index > size) {
return;
}
if (index == 0) {
this.addFirst(val);
return;
}
if (index == size) {
this.addLast(val);
return;
}
ListNode curNode = this.head;
for (int i = 0; i < index - 1; ++i) {
curNode = curNode.next;
}
ListNode newNode = new ListNode(val);
newNode.next = curNode.next;
curNode.next = newNode;
}
// 尾插
public void addLast(int val) {
if (this.head == null) {
this.addFirst(val);
return;
}
ListNode newNode = new ListNode(val);
ListNode curNode = this.head;
while (curNode.next != null) {
curNode = curNode.next;
}
curNode.next = newNode;
}
// 头插
public void addFirst(int val) {
ListNode newNode = new ListNode(val);
newNode.next = this.head;
this.head = newNode;
}
// 清空链表
public void clear() {
this.head = null;
}
// 结点数量
public int size() {
int size = 0;
for (ListNode curNode = this.head; curNode != null; curNode = curNode.next) {
++size;
}
return size;
}
// 打印所有结点
public void display() {
System.out.print("[");
for (ListNode curNode = this.head; curNode != null; curNode = curNode.next) {
System.out.print(curNode.val);
if (curNode.next == null) {
break;
}
System.out.print(", ");
}
System.out.println("]");
}
}
class ListNode {
public int val;
public ListNode next = null;
public ListNode(int val) {
this.val = val;
}
}
自己实现的MyLinkedList
public class MyLinkedList {
private static class ListNode {
int val;
ListNode next = null;
ListNode prev = null;
public ListNode(int val) {
this.val = val;
}
}
private ListNode head = new ListNode(-1);;
private int length = 0;
public MyLinkedList() {
this.head.next = this.head;
this.head.prev = this.head;
}
public static void main(String[] args) {
MyLinkedList list = new MyLinkedList();
list.addFirst(1);
list.display();
list.addLast(2);
list.addLast(3);
list.addLast(4);
list.display();
list.removeFirst();
list.display();
list.removeLast();
list.display();
list.add(1, 4);
list.display();
list.removeByIndex(1);
list.display();
list.removeByValue(2);
list.display();
list.get(0);
list.display();
list.set(0, 2);
list.display();
}
// 求链表的长度
public int length() {
return this.length;
}
public void display() {
ListNode cur = head.next;
for(cur = head.next; cur != head; cur = cur.next) {
System.out.print(cur.val + " ");
}
System.out.println();
}
// 头插
public void addFirst(int val) {
ListNode cur = new ListNode(val);
head.next = cur;
cur.prev = head;
cur.next = head;
head.prev = cur;
length++;
}
// 尾插
public void addLast(int val) {
ListNode cur = new ListNode(val);
head.prev.next = cur;
cur.prev = head.prev;
cur.next = head;
head.prev = cur;
length++;
}
// 头删
public void removeFirst() {
ListNode cur = this.head.next;
cur.next.prev = cur.prev;
cur.prev.next = cur.next;
length--;
}
// 尾删
public void removeLast() {
ListNode cur = head.prev;
cur.prev.next = cur.next;
cur.next.prev = cur.prev;
length--;
}
// 指定位置插入
public void add(int index, int val) {
if(index == 0) {
addFirst(val);
return;
}
if(index == length) {
addLast(val);
return;
}
ListNode cur = head.next;
ListNode newNode = new ListNode(val);
for(int i = 0; i < index; i++) {
cur = cur.next;
}
cur.prev.next = newNode;
newNode.prev = cur.prev;
newNode.next = cur;
cur.prev = newNode;
length++;
}
// 指定位置删除
public void removeByIndex(int index) {
if(index < 0) {
return;
}
if(index == 0) {
removeFirst();
return;
}
if(index == length) {
removeLast();
return;
}
ListNode cur = head.next;
for(int i = 0; i < index; i++) {
cur = cur.next;
}
cur.prev.next = cur.next;
cur.next.prev = cur.prev;
length--;
}
// 按值删除
public void removeByValue(int val) {
ListNode cur = head.next;
for(cur = head.next; cur != head; cur = cur.next) {
if(cur.val == val) {
cur.prev.next = cur.next;
cur.next.prev = cur.prev;
length--;
return;
}
}
}
// 获取指定下标节点的值
public int get(int index) {
ListNode cur = head.next;
if(index < length) {
for(int i = 0; i < index; i++) {
cur = cur.next;
}
return cur.val;
}
return 0;
}
// 修改
public void set(int index, int value) {
ListNode cur = head.next;
if(index < length) {
for(int i = 0; i < index; i++) {
cur = cur.next;
}
cur.val = value;
}
}
}
