|
目录
1.无头单向非循环链表
1.1 定义链表的节点对象
1.2 打印链表
1.3 得到链表的长度
1.4 头插法add
1.5 尾插法add
1.6 从任意位置插入的add
1.7 查找包含关键字key的节点是否在链表中
1.8 删除第一次出现关键字为key的节点
1.9 删除链表中所有值为key的节点
1.10 清空链表
2.无头双向非循环链表
2.1 无头双向链表节点的定义
2.2 头插法add
2.2 尾插法add
2.3 随机位置插入add
2.4 删除第一次出现关键字为key的节点
2.5 删除所有关键字为key的节点
2.6 清空链表
2.7 打印链表、获取链表长度、查找关键字key
1.无头单向非循环链表
无头单向非循环链表指的是：一个单向链表中没有头结点，链表中不构成循环的链表。（循环链表：最后一个节点指向头）
下面我们模拟实现一下单链表（后面都简称单链表）
1.1 定义链表的节点对象
我们首先定义一个类：MySingleList 里面实现对链表进行操作的一些方法，在MySingleList类中定义一个内部类：ListNode?是节点对象，里面存放节点的数据和指向下一个节点的引用变量，在MySingleList类中我们定义一个ListNode引用用来标记链表的头
public class MySingleList {
public ListNode head;
static class ListNode {
public int val;
public ListNode next;
public ListNode(int val) {
this.val = val;
}
}
}
1.2 打印链表
想要打印链表里面的所有元素，需要遍历链表，因为我们不希望指向头head的引用的指向发生改变，所以需要定义一个ListNode的引用变量代替head去改变（后面基本都会用到）
判断循环终止的条件是cur != null 当cur的指向为空时，说明链表已经遍历结束，并且如果链表本身结束空的，那么根本就不会进入循环，不会造成空指针异常，接下来进行每一项的打印即可。
public void disPlay() {
ListNode cur = this.head;
while (cur != null) {
System.out.print(cur.val + " ");
cur = cur.next;
}
System.out.println();
}
1.3 得到链表的长度
方法与上面类似，首先对链表为空的情况进行判断，如果链表是空，那么返回-1进行提示（如果觉得没必要也可以不写），然后设置一个计数器，链表每向后走一步，计数器++，最后返回计数器。
//得到单链表的长度
public int size() {
if (this.head == null) {
return -1;
}
ListNode cur = this.head;
int count = 0;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
1.4 头插法add
运用头插法需要重新设置链表的头，首先初始化一个新节点，让新节点的next引用指向当前的头结点，然后让head指向新节点。
//头插法
public void addFirst(int data) {
ListNode node = new ListNode(data);
node.next = this.head;
this.head = node;
}
1.5 尾插法add
首先判断链表是否为空，如果为空那么直接让head指向新节点，若不为空，就遍历到链表尾部节点，让尾部节点的next指向新节点。
//尾插法
public void addLast(int data) {
ListNode cur = this.head;
ListNode node = new ListNode(data);
if (this.head == null) {
this.head = node;
} else {
while (cur.next != null) {
cur = cur.next;
}
cur.next = node;
}
}
1.6 从任意位置插入的add
首先要对传过来的index进行合法性的判断，如果index不在链表的长度范围内，则报出异常，之后判断index是否为链表的头和尾，如果是咋调用头插法或尾插法。
经过上面的层层筛选，就运用findIndex方法在链表中寻找index - 1的位置，用cur接收，然后插入新节点。
插入新节点：先另新节点的next指向cur位置节点的next，然后让cur节点的next指向新节点。
//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index, int data) {
if (index < 0 || index > this.size()) {
throw new IndexWrongFulException("index位置不合法");
}
if (index == 0) {
this.addFirst(data);
return;
}
if (index == this.size()) {
this.addLast(data);
return;
}
ListNode cur = findIndex(index);
ListNode node = new ListNode(data);
node.next = cur.next;
cur.next = node;
}
private ListNode findIndex(int index) {
ListNode cur = this.head;
while (index - 1 != 0) {
cur = cur.next;
index--;
}
return cur;
}
//异常的代码
public class IndexWrongFulException extends RuntimeException {
public IndexWrongFulException() {
}
public IndexWrongFulException(String message) {
super(message);
}
}
1.7 查找包含关键字key的节点是否在链表中
遍历链表，如果节点的val == key则返回true，遍历结束还没找到则返回false
//查找是否包含关键字key是否在单链表当中
public boolean contains(int key) {
ListNode cur = this.head;
while (cur != null) {
if (cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}
1.8 删除第一次出现关键字为key的节点
首先进行两个判断：1.链表是否为空 2.链表的head是否是key（如果是key则让head指向下一个节点，达到删除的目的）
之后用findKey方法遍历链表，寻找元素key，如果返回值为空则链表中没有该元素，如果不是空，则删除返回的元素。
//删除第一次出现关键字为key的节点=
public void remove(int key) {
if (this.head == null) {
return;
}
if (this.head.val == key) {
this.head = this.head.next;
return;
}
ListNode cur = findKey(key);
if (cur == null) {
System.out.println("链表中没有你想要删除的数据");
return;
}
ListNode del = cur.next;
cur.next = del.next;
}
private ListNode findKey(int key) {
ListNode cur = this.head;
while (cur.next != null) {
if (cur.next.val == key) {
return cur;
}
cur = cur.next;
}
return null;
}
1.9 删除链表中所有值为key的节点
首先判断链表是否为空，然后设置两个引用变量prev指向head，cur指向head的next，若cur的指向值为key则让前一个指向的next指向cur的next达到删除节点的目的，如果不是，则prev指向cur去判断下一个节点。最后判断head的值是否是key。
//删除所有值为key的节点
public void removeAllKey(int key) {
if (this.head == null) {
return;
}
ListNode cur = this.head.next;
ListNode prev = this.head;
while (cur != null) {
if (cur.val == key) {
prev.next = cur.next;
} else {
prev = cur;
}
cur = cur.next;
}
if (this.head.val == key) {
this.head = this.head.next;
}
}
1.10 清空链表
直接将head置空，让后面的节点都失去引用他们的对象，达到释放空间的目的。
//清空链表
public void clear() {
this.head = null;
}
2.无头双向非循环链表
双向链表和单向链表的区别是 双向链表的每一个节点都可以访问它的前一个节点和后一个节点，而单向链表只能访问后一个节点
2.1 无头双向链表节点的定义
和单链表大致相同，不同的是节点中多了一个前向引用，链表中多了一个尾部节点 tail 的引用。
public class MyLinkedList {
static class ListNode {
public int val;
public ListNode prev;
public ListNode next;
public ListNode(int val) {
this.val = val;
}
}
public ListNode head;
public ListNode tail;
}
2.2 头插法add
因为多了一个尾部引用所以在插入的时候需要考虑的细节更多。
首先判断head是否为空，如果为空让头引用和尾引用都指向这个新节点
不为空则进行插入操作，先让新节点的next指向头引用，让头引用的前驱指向新节点，在将头引用的指向改为新节点（头引用的前驱一直为null 尾引用的后驱一直为空）。
public void addFirst(int data) {
ListNode node = new ListNode(data);
if(this.head == null) {
this.head = node;
this.tail = node;
} else {
node.next = this.head;
this.head.prev = node;
this.head = node;
}
}
2.2 尾插法add
和头插法类似，尾引用为空让head和tail指向新节点，不为空则进行插入操作
//尾插法
public void addLast(int data) {
ListNode node = new ListNode(data);
if(this.head == null) {
this.head = node;
this.tail = node;
} else {
node.prev = this.tail;
this.tail.next = node;
this.tail = node;
}
}
2.3 随机位置插入add
首先判断index的数值是否合法，不合法报异常，如果index为0和index为尾则调用头插法或者尾插法，经过上面的判断之后剩下的index一定是中间位置，然后找到index位置的节点，在它前面插入新元素，一共四部：1.更改新节点的前驱 2.更改新节点的后驱 3.更改新节点后驱的前驱 4.更改新节点前驱的后驱
//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index, int data) {
if(index < 0 || index > this.size()) {
throw new IndexWrongFulException("index位置不合法");
}
if(index == 0) {
this.addFirst(data);
return;
}
if(index == this.size()) {
this.addLast(data);
return;
}
ListNode cur = findIndex(index);
ListNode node = new ListNode(data);
node.prev = cur.prev;
node.next = cur;
cur.prev.next = node;
cur.prev = node;
}
private ListNode findIndex(int index) {
ListNode cur = this.head;
while(index != 0) {
cur = cur.next;
index--;
}
return cur;
}
//异常
public class IndexWrongFulException extends RuntimeException {
public IndexWrongFulException() {
}
public IndexWrongFulException(String message) {
super(message);
}
}
2.4 删除第一次出现关键字为key的节点
首先判断链表是否为空，之后进入循环查找为key的节点
1.当key节点为head 无论什么情况都可以先让head指向head的后驱 之后进行判断
1.1 当前head为空：让tail指向head
1.2 不为空：更改head的前驱为null
2.key不是head
2.1 key是tail：让tail指向tail的前驱，在将当前tail的后驱置空
2.2 key不是tail：那么key就是中间节点，让key前驱的后驱指向key的后驱，key后驱的前驱指向key的前驱
如果链表中有key节点那么进行删除后return，如果链表中没有则跳出循环
//删除第一次出现关键字为key的节点
public void remove(int key) {
if(this.head == null) {
System.out.println("当前链表为空");
return;
}
ListNode cur = head;
while(cur != null) {
if(cur.val == key) {
if(cur == this.head) {
this.head = this.head.next;
if(this.head == null) {
tail = null;
} else {
this.head.prev = null;
}
} else {
if(cur == this.tail) {
this.tail = this.tail.prev;
this.tail.next = null;
} else {
cur.next.prev = cur.prev;
cur.prev.next = cur.next;
}
}
return;
}
cur = cur.next;
}
System.out.println("当前链表中没有你想要删除的元素");
}
2.5 删除所有关键字为key的节点
上讲解了删除一个节点的，当删除一个节点之后就进行了return，那么想删除所有为key的节点就只需要把return去掉即可。
//删除所有值为key的节点
public void removeAllKey(int key) {
ListNode cur = head;
while(cur != null) {
if(cur.val == key) {
if(cur == this.head) {
this.head = this.head.next;
if(this.head == null) {
this.tail = null;
} else {
this.head.prev = null;
}
} else {
if(cur == this.tail) {
this.tail = this.tail.prev;
this.tail.next = null;
} else {
cur.next.prev = cur.prev;
cur.prev.next = cur.next;
}
}
}
cur = cur.next;
}
}
2.6 清空链表
清空双向链表没办法像清空单向链表那么简单粗暴，因为双向链表的每个节点都会有指向前驱和后驱的引用，只置空头尾节点，中间的节点会一直存在占用内存，所以需要一个循环将所有的节点置空，最后剩下头尾节点，在进行置空即可。
public void clear() {
ListNode cur = this.head;
while(cur != null) {
ListNode curNext = cur.next;
cur.next = null;
cur.prev = null;
cur = curNext;
}
this.head = null;
this.tail = null;
}
2.7 打印链表、获取链表长度、查找关键字key
上面的这些方法和单链表相同，这里直接给出原码
//打印链表
public void display() {
ListNode cur = this.head;
while(cur != null) {
System.out.print(cur.val + " ");
cur = cur.next;
}
System.out.println();
}
//得到单链表的长度
public int size() {
int count = 0;
ListNode cur = this.head;
while(cur != null) {
cur = cur.next;
count++;
}
return count;
}
//查找是否包含关键字key是否在单链表当中
public boolean contains(int key) {
ListNode cur = this.head;
while(cur != null) {
if(cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}
|