<h2>一、链表的概念和结构</h2>
<h3>1.1 链表的概念</h3>
<blockquote>
<p>简单来说链表是物理上不一定连续，但是逻辑上一定连续的一种数据结构</p>
</blockquote>
<h3>1.2 链表的分类</h3>
<blockquote>
<p>实际中链表的结构非常多样，以下情况组合起来就有8种链表结构. 单向和双向，带头和不带头，循环和非循环。排列组合和会有8种。<br>
但我这只是实现两种比较难的链表，理解之后其它6种就比较简单了<br>
1.单向不带头非循环链表<br>
2.双向不带头非循环链表</p>
</blockquote>
<h2>二、单向不带头非循环链表</h2>
<p style="text-align: center"><img alt="在这里插入图片描述" src="https://beijingoptbbs.oss-cn-hangzhou.aliyuncs.com/jb/2426819-95e058ca24812af348e05554215396bc.png"></p>
<h3>2.1 创建节点类型</h3>
<blockquote>
<p>我们创建了一个 ListNode 类为节点类型，里面有两个成员变量，val用来存储数值，next来存储下一个节点的地址。<br>
还有一个带一个参数的构造方法在实例化对象的同时给val赋值，因为我们不知道下一个节点的地址所以next是默认值一个null</p>
</blockquote>
<div class="blockcode">
<pre class="brush:java;">
class ListNode {
public int val;//数值
public ListNode next;//下一个节点的地址
public ListNode(int val) {
this.val = val;
}
}</pre>
</div>
<p>我们在 MyLinkedList 里创建一个head变量来标识链表的头部，接着就是实现单链表的增删查改了</p>
<p style="text-align: center"><img alt="在这里插入图片描述" src="https://beijingoptbbs.oss-cn-hangzhou.aliyuncs.com/jb/2426819-7bb308634e67d5e4329068646578fcf2.png"></p>
<h3>2.2 头插法</h3>
<p style="text-align: left">这个头插法并不要考虑第一次插入，每次插入只需要把插入的节点node 的next值改成头节点，再把头节点指向node</p>
<p style="text-align: center"><img alt="在这里插入图片描述" src="https://beijingoptbbs.oss-cn-hangzhou.aliyuncs.com/jb/2426819-55307037f371dd3b5f3b088197b938ae.png"></p>
<div class="blockcode">
<pre class="brush:java;">
//头插法
public void addFirst(int data) {
ListNode node = new ListNode(data);
node.next = this.head;
this.head = node;
}</pre>
</div>
<h3>2.3 尾插法</h3>
<blockquote>
<p>尾插法首先要考虑是不是第一次插入，如果是的话直接把head指向node就好了，如果不是第一次插入，则需要定义一个cur来找尾巴节点，把尾巴节点的next值改成node就好了。因为如果不用尾巴节点的话，head就无法标识到头部了</p>
</blockquote>
<p style="text-align: center"><img alt="在这里插入图片描述" src="https://beijingoptbbs.oss-cn-hangzhou.aliyuncs.com/jb/2426819-7422fdb1da3687df49a8b46faadf79c2.png"></p>
<div class="blockcode">
<pre class="brush:java;">
//尾插法
public void addLast(int data) {
ListNode node = new ListNode(data);
ListNode cur = this.head;
//第一次插入
if(this.head == null) {
this.head = node;
}else{
while (cur.next != null) {
cur = cur.next;
}
cur.next = node;
}
}
</pre>
</div>
<h3>2.4 获取链表长度</h3>
<blockquote>
<p>定义一个计数器count，当cur遍历完链表的时候直接返回count就好</p>
</blockquote>
<div class="blockcode">
<pre class="brush:java;">
//得到单链表的长度
public int size() {
int count = 0;
ListNode cur = this.head;
while (cur != null) {
cur = cur.next;
count++;
}
return count;
}
</pre>
</div>
<h3>2.5 任意位置插入</h3>
<blockquote>
<p>我们假设链表的头是从0位置开始的，任意位置插入需要考虑几点<br>
1.位置的合法性，如果位置小于0，或者大于链表长度则位置不合法<br>
2.如果要插入的是0位置直接使用头插法<br>
3.如果插入的位置等于链表长度则使用尾插法，因为我们这链表是从0开始的</p>
</blockquote>
<p>最关键的就是从中间任意位置插入 要从中间位置插入，就需要找到要插入位置的前一个节点的位置。再插入到它们中间。</p>
<p style="text-align: center"><img alt="在这里插入图片描述" src="https://beijingoptbbs.oss-cn-hangzhou.aliyuncs.com/jb/2426819-60b15d3e2aa5b1c3b04f331b33e964b9.png"></p>
<div class="blockcode">
<pre class="brush:java;">
/**
* 让 cur 向后走 index - 1 步
* @param index
* @return
*/
public ListNode findIndexSubOne(int index) {
int count = 0;
ListNode cur = this.head;
while (count != index-1) {
cur = cur.next;
count++;
}
return cur;
}
//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index,int data) {
//判断合法性
if(index < 0 || index > size()) {
System.out.println("index位置不合法");
return;
}
//头插法
if(index == 0) {
this.addFirst(data);
return;
}
//尾插法
if(index == size()) {
this.addLast(data);
return;
}
//找前驱,cur指向的是 index 的前一个节点
ListNode cur = findIndexSubOne(index);
ListNode node = new ListNode(data);
node.next = cur.next;
cur.next |
|
转播
