链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。
单向链表(无序链表)(Single-Linked List)使用链表结构可以克服数组需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。
单链表是链表中结构最简单的。一个单链表的节点(Node)分为两个部分，第一个部分
(data)保存或者显示关于节点的信息，另一个部分存储下一个节点的地址。最后一个节点存储地址的部分指向空值。链表有一个头节点。
public class Node {
//节点值
private Integer data;
//下个节点信息
private Node next;
public Node(Integer data, Node next) {
this.data = data;
this.next = next;
}
public Integer getData() {
return data;
}
public void setData(Integer data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
我们创建一个类来实现基本的单向链表
class MySingleLinkedList{
//头节点
private Node head;
public Node getHead() {
return head;
}
public void setHead(Node head) {
this.head = head;
}
｝
- 插入
public void pushHead(int data) {
Node node = new Node(data, head);
head = node;
}
public void pushTail(int data) {
Node node = new Node(data, null);
if (head.getData() == null) {
head = node;
}
Node currentNode = head;
while (true) {
if (currentNode.getNext() == null) {
currentNode.setNext(node);
break;
}
currentNode = currentNode.getNext();
}
}
- 查找
public Node find(int data) {
if (head == null) {
return null;
}
Node node;
Node currentNode = head;
while (true) {
if (currentNode == null || currentNode.getData() == data) {
node = currentNode;
break;
}
currentNode = currentNode.getNext();
}
return node;
}
- 删除
public void deleteHead() {
if (head != null) {
head = head.getNext();
}
}
public void deleteTail() {
if (head != null) {
Node currentNode = head;
while (true) {
if (currentNode.getNext() == null) {
break;
}
if (currentNode.getNext().getNext() == null) {
currentNode.setNext(null);
break;
}
currentNode = currentNode.getNext();
}
}
}
public void delete(int data) {
if (head != null) {
if (head.getData() == data) {
deleteHead();
return;
}
//当前节点
Node currentNode = head;
//当前节点父级节点信息
Node dadNode = head;
while ((currentNode = currentNode.getNext()) != null) {
if (currentNode.getData() == data) {
dadNode.setNext(currentNode.getNext());
}
dadNode = currentNode;
}
}
}
- 遍历
public void forEach() {
if (head != null) {
Node currentNode = head;
do {
System.out.print(currentNode.getData() + " --> ");
} while ((currentNode = currentNode.getNext()) != null);
System.out.print("null");
System.out.println();
}
}
测试
Node head = new Node(12, null);
MySingleLinkedList mySingleLinkedList = new MySingleLinkedList(head);
mySingleLinkedList.pushHead(10);
mySingleLinkedList.pushTail(99);
mySingleLinkedList.pushTail(1);
mySingleLinkedList.pushHead(2);
mySingleLinkedList.forEach();
mySingleLinkedList.deleteHead();
mySingleLinkedList.deleteTail();
mySingleLinkedList.delete(12);
mySingleLinkedList.forEach();
结果
2 --> 10 --> 12 --> 99 --> 1 --> null 10 --> 99 --> null双端链表
双端链表是单向链表周的一种，他在原有的单向链表上加了个尾节点，对于尾部操作更加便捷。
class MyDoubleLinked{
//头节点
private Node head;
// 尾节点
private Node tail;
public Node getHead() {
return head;
}
public void setHead(Node head) {
this.head = head;
}
public Node getTail() {
return tail;
}
public void setTail(Node tail) {
this.tail = tail;
}
}
- 插入
public void pushHead(int data) {
Node node = new Node(data, head);
head = node;
}
public void pushTail(int data) {
if (head == null) {
pushHead(data);
} else {
Node node = new Node(data, null);
tail.setNext(node);
tail = node;
}
}
- 查找
public Node find(int data) {
if (head == null) {
return null;
}
Node node;
Node currentNode = head;
while (true) {
if (currentNode == null || currentNode.getData() == data) {
node = currentNode;
break;
}
currentNode = currentNode.getNext();
}
return node;
}
- 删除
public void deleteHead() {
if (head != null) {
head = head.getNext();
}
}
public void deleteTail() {
if (head != null) {
Node currentNode = head;
while (true) {
if (currentNode.getNext() == null) {
break;
}
if (currentNode.getNext().getNext() == null) {
currentNode.setNext(null);
tail = currentNode;
break;
}
currentNode = currentNode.getNext();
}
}
}
public void delete(int data) {
if (head != null) {
if (head.getData() == data) {
deleteHead();
return;
}
//当前节点
Node currentNode = head;
//当前节点父级节点信息
Node dadNode = head;
while ((currentNode = currentNode.getNext()) != null) {
if (currentNode.getData() == data) {
dadNode.setNext(currentNode.getNext());
}
dadNode = currentNode;
}
}
}
- 遍历
public void forEach() {
if (head != null) {
Node currentNode = head;
do {
System.out.print(currentNode.getData() + " --> ");
} while ((currentNode = currentNode.getNext()) != null);
System.out.print("null");
System.out.println();
}
}
测试
Node head = new Node(12, null);
MySingleLinkedList mySingleLinkedList = new MySingleLinkedList(head);
mySingleLinkedList.pushHead(10);
mySingleLinkedList.pushTail(99);
mySingleLinkedList.pushTail(1);
mySingleLinkedList.pushHead(2);
mySingleLinkedList.forEach();
mySingleLinkedList.deleteHead();
mySingleLinkedList.deleteTail();
mySingleLinkedList.delete(12);
mySingleLinkedList.forEach();
结果
2 --> 10 --> 12 --> 99 --> 1 --> null 10 --> 99 --> null
