目录
1. 概况
链表在逻辑上是连续的,在物理上不一定连续。
分类:
- 单向、双向
- 带头、不带头
- 循环、非循环
2. 思路
data:数值域,里面存储的数据
next:引用变量 -> 下一个节点的地址
尾巴节点:当这个节点的next域为null的时候
头节点:整个链表当中的第一个节点
单向不带头非循环链表:
单向带头非循环链表:
单向不带头循环链表:
3. 定义链表节点
class Node {
public int val;
public Node next;
public Node(int data) {
this.data = data;
}
}
4. 实现方法
//生成链表
public void createList()
//打印链表内容
public void display()
//打印链表长度
public int length()
//查找是否包含关键字key在链表当中
public boolean contains(int key)
//头插法
public void addFirst(int data)
//尾插法
public void addLast(int data)
//找到前一个地址
public Node searchPrev(int index)
//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index,int data)
//找关键字key的前驱
public Node searchPrevNode(int key)
//删除第一次出现关键字为key的节点
public void remove(int key)
//删除所有值为key的节点
public void removeAllKey(int key)
//清空链表
public void clear()
5. 源代码
MyLinkedList.java
class Node {
public int data;
public Node next;
public Node(int data) {
this.data = data;
}
}
public class MyLinkedList {
public Node head;//标识单链表的头节点
public void createList() {
Node node1 = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);
Node node4 = new Node(4);
Node node5 = new Node(5);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
this.head = node1;
}
//打印链表内容
public void display() {
Node cur = this.head;
while(cur != null) {
System.out.print(cur.data+" ");
cur = cur.next;
}
System.out.println();
}
//打印链表长度
public int length() {
int count = 0;
Node cur = this.head;
while (cur != null) {
cur = cur.next;
count++;
}
return count;
}
//查找是否包含关键字key在链表当中
public boolean contains(int key) {
Node cur = this.head;
while (cur != null) {
if(cur.data == key) {
return true;
}
cur = cur.next;
}
return false;
}
//头插法
public void addFirst(int data) {
Node node = new Node(data);
if (this.head == null) {
this.head = node;
} else {
node.next = this.head;
this.head = node;
}
}
//尾插法
public void addLast(int data) {
Node node = new Node(data);
if (this.head == null) {
this.head = node;
} else {
Node cur = this.head;
while (cur.next != null) {
cur = cur.next;
}
cur.next = node;
}
}
//找到前一个地址
public Node searchPrev(int index) {
Node cur = this.head;
int count = 0;
while (count != index-1) {
cur = cur.next;
count++;
}
return cur;
}
//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index, int data) {
if (index < 0 || index > length()) {
throw new RuntimeException("插入位置错误");
}
//头插法
if (index == 0) {
addFirst(data);
return;
}
//尾插法
if (index == length()) {
addLast(data);
return;
}
Node cur = searchPrev(index);
Node node = new Node(data);
node.next = cur.next;
cur.next = node;
}
//找关键字key的前驱
public Node searchPrevNode(int key) {
Node cur = this.head;
while (cur.next != null) {
if (cur.next.data == key) {
return cur;
}
cur = cur.next;
}
return null;
}
//删除第一次出现的关键字key
public void remove(int key) {
if (this.head == null) return;
//单独判断头节点的问题
if (this.head.data == key) {
this.head = this.head.next;
return;
}
Node cur = searchPrevNode(key);
if (cur == null) {
System.out.println("没有你要删除的节点!");
return;
}
Node del = cur.next;
cur.next = del.next;
}
//删除所有值为key的节点
public void removeAllKey(int key) {
if (this.head == null) {
return;
}
Node prev = this.head;
Node cur = this.head.next;
while (cur != null) {
if(cur.data == key) {
prev.next = cur.next;
cur = cur.next;
} else {
prev = cur;
cur = cur.next;
}
}
//最后判断头节点
if (this.head.data == key) {
this.head = this.head.next;
}
}
//清空链表
public void clear() {
while (this.head != null) {
Node curNext = this.head.next;
this.head.next = null;
this.head = curNext;
}
}
}
test.java
测试代码
public class test {
public static void main(String[] args) {
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.createList();
myLinkedList.display();//1 2 3 4 5
System.out.println(myLinkedList.length());
myLinkedList.remove(1);
myLinkedList.display();//2 3 4 5
}
}