链表（Linked List）
1、链表介绍
链表是有序的列表，但是他在内存中的存储结构如下：
链表是以节点的方式来存储的，是链式存储每个节点包含data域、next域:指向下一个节点链表的各个节点不一定是连续存储。链表分带头节点的链表和不带头节点的链表，根据实际情况来确定 单链表（带头节点）逻辑结构示意图
2、单链表应用
使用带头节点的单向链表实现-开发语言排行榜管理，完成对语言的增删改查操作。
2.1、定义链表结构
分析：
使用带头节点的链表，我们需要定义头节点属性；链表包涵data域和next域，我们这里需要排序新增no排序属性、name语言名称属性 我们定义如下Node结构：
/**
* 单链表节点
*/
public class LanguageNode {
/**
* 排序
*/
private int no;
/**
* 语言名称
*/
private String language;
/**
* 语言描述
*/
private String languageDescribe;
/**
* 下个节点
*/
private LanguageNode next;
public LanguageNode(int no, String language, String languageDescribe, LanguageNode next) {
this.no = no;
this.language = language;
this.languageDescribe = languageDescribe;
this.next = next;
}
@Override
public String toString() {
return "LanguageNode{" +
"no=" + no +
", language='" + language + '\'' +
", languageDescribe='" + languageDescribe + '\'' +
'}';
}
}
2.2 新增节点
我们定义个SingleLinkedList链表管理器，在链表管理器中完成链表的增删改查操作。
下面我们实现链表的新增操作：
第一种方式在添加语言时，直接添加在链表的尾部
思路分析示意图：
第二种在添加语言时，根据排名将语言插入到相应的位置（如果有这个排名，则添加失败，并给出提示）
思路分析示意图
代码实现：
/**
* 根据顺序添加节点
*
* @param node 添加数据
* @return 当前节点
*/
public LanguageNode addByOrder(LanguageNode node) {
//因为头节点不能移动，定义临时变量tmp
LanguageNode tmp = this.head;
//定义链表添加标识符
boolean flag = false;
while (true) {
if (tmp.next == null) {
break;
}
if (tmp.next.no > node.no) {
break;
} else if (tmp.next.no == node.no) {
//说明该顺序已经存在
flag = true;
break;
}
tmp = tmp.next;
}
if (flag) {
System.out.printf("插入的位置%d已存在，不能插入\n", node.no);
} else {
node.next = tmp.next;
tmp.next = node;
}
return node;
}
/**
* 添加节点
*
* @param node 添加数据
* @return
*/
public LanguageNode add(LanguageNode node) {
//因为头节点不能移动，定义临时变量tmp
LanguageNode tmp = this.head;
//将数据添加到最后，便利链表
while (tmp.next != null) {
tmp = tmp.next;
}
tmp.next = node;
return node;
}
测试：
首先使用add尾部添加
public static void main(String[] args) {
SingleLinkedList linkedList = new SingleLinkedList();
LanguageNode java = new LanguageNode(1, "java", "超级好用");
LanguageNode python = new LanguageNode(2, "python", "python");
LanguageNode goLang = new LanguageNode(3, "goLang", "goLang");
LanguageNode js = new LanguageNode(4, "js", "js");
LanguageNode php = new LanguageNode(5, "php", "php是世界上最好的语言");
linkedList.add(python);
linkedList.add(java);
linkedList.add(js);
linkedList.add(php);
linkedList.add(goLang);
linkedList.list();
}
执行结果如下：
从结果看出：打印的顺序和我们插入的顺序一致，没有按照no进行排序操作
使用addByOrder测试
public static void main(String[] args) {
SingleLinkedList linkedList = new SingleLinkedList();
LanguageNode java = new LanguageNode(1, "java", "超级好用");
LanguageNode python = new LanguageNode(2, "python", "python");
LanguageNode goLang = new LanguageNode(3, "goLang", "goLang");
LanguageNode js = new LanguageNode(4, "js", "js");
LanguageNode php = new LanguageNode(5, "php", "php是世界上最好的语言");
linkedList.addByOrder(python);
linkedList.addByOrder(java);
linkedList.addByOrder(js);
linkedList.addByOrder(php);
linkedList.addByOrder(goLang);
linkedList.list();
}
执行结果如下：
从结果看出：打印的顺序和我们插入的顺序不致，按照no进行排序插入。
2.3 修改节点信息
思路：修改节点功能比较简单，通过遍历先找到该节点信息，在对该节点内容进行修改即可。 代码实现
public void update(LanguageNode node) {
LanguageNode tmp = this.head;
if (tmp.next == null) {
System.out.println("链表为空");
return;
}
while (true) {
if (tmp.next == null) {
System.out.println("被修改的数据不存在");
break;
}
if (tmp.next.no == node.no) {
node.next = tmp.next.next;
tmp.next = node;
break;
}
tmp = tmp.next;
}
}
2.4 删除节点
思路：先找到被删除的节点的前一个节点，定义为temp,我们将temp.next=temp.next.next将节点的饮用指要删除的向下个节点。
代码实现：
public void delete(LanguageNode node) {
LanguageNode tmp = this.head;
if (tmp.next == null) {
System.out.println("链表为空");
return;
}
while (true) {
if (tmp.next == null) {
System.out.println("被删除的数据不存在");
break;
}
if (tmp.next.no == node.no) {
tmp.next = tmp.next.next;
break;
}
tmp = tmp.next;
}
}
以上完成了链表的增删改查；
附录：完整代码
public class SingleLinkedList {
/**
* 定义头节点
*/
private LanguageNode head = new LanguageNode(0, "", "");
public static void main(String[] args) {
SingleLinkedList linkedList = new SingleLinkedList();
LanguageNode java = new LanguageNode(1, "java", "超级好用");
LanguageNode python = new LanguageNode(2, "python", "python");
LanguageNode goLang = new LanguageNode(3, "goLang", "goLang");
LanguageNode js = new LanguageNode(4, "js", "js");
LanguageNode php = new LanguageNode(5, "php", "php是世界上最好的语言");
LanguageNode node = new LanguageNode(4, "node", "node");
linkedList.addByOrder(python);
linkedList.addByOrder(java);
linkedList.addByOrder(js);
linkedList.addByOrder(php);
linkedList.addByOrder(goLang);
linkedList.update(node);
linkedList.delete(node);
linkedList.list();
}
public void delete(LanguageNode node) {
LanguageNode tmp = this.head;
if (tmp.next == null) {
System.out.println("链表为空");
return;
}
while (true) {
if (tmp.next == null) {
System.out.println("被删除的数据不存在");
break;
}
if (tmp.next.no == node.no) {
tmp.next = tmp.next.next;
break;
}
tmp = tmp.next;
}
}
public void update(LanguageNode node) {
LanguageNode tmp = this.head;
if (tmp.next == null) {
System.out.println("链表为空");
return;
}
while (true) {
if (tmp.next == null) {
System.out.println("被修改的数据不存在");
break;
}
if (tmp.next.no == node.no) {
node.next = tmp.next.next;
tmp.next = node;
break;
}
tmp = tmp.next;
}
}
/**
* 根据顺序添加节点
*
* @param node 添加数据
* @return 当前节点
*/
public LanguageNode addByOrder(LanguageNode node) {
//因为头节点不能移动，定义临时变量tmp
LanguageNode tmp = this.head;
//定义链表添加标识符
boolean flag = false;
while (true) {
if (tmp.next == null) {
break;
}
if (tmp.next.no > node.no) {
break;
} else if (tmp.next.no == node.no) {
//说明该顺序已经存在
flag = true;
break;
}
tmp = tmp.next;
}
if (flag) {
System.out.printf("插入的位置%d已存在，不能插入\n", node.no);
} else {
node.next = tmp.next;
tmp.next = node;
}
return node;
}
/**
* 添加节点
*
* @param node 添加数据
* @return
*/
public LanguageNode add(LanguageNode node) {
//因为头节点不能移动，定义临时变量tmp
LanguageNode tmp = this.head;
//将数据添加到最后，便利链表
while (tmp.next != null) {
tmp = tmp.next;
}
tmp.next = node;
return node;
}
public void list() {
LanguageNode tmp = this.head;
if (tmp.next == null) {
System.out.println("链表为空");
}
while (tmp.next != null) {
System.out.println(tmp.next);
tmp = tmp.next;
}
}
/**
* 单链表节点
*/
public static class LanguageNode {
/**
* 排序
*/
private int no;
/**
* 语言名称
*/
private String language;
/**
* 语言描述
*/
private String languageDescribe;
/**
* 下个节点
*/
private LanguageNode next;
public LanguageNode(int no, String language, String languageDescribe) {
this.no = no;
this.language = language;
this.languageDescribe = languageDescribe;
this.next = null;
}
public int getNo() {
return no;
}
public String getLanguage() {
return language;
}
public String getLanguageDescribe() {
return languageDescribe;
}
public LanguageNode getNext() {
return next;
}
@Override
public String toString() {
return "LanguageNode{" +
"no=" + no +
", language='" + language + '\'' +
", languageDescribe='" + languageDescribe + '\'' +
'}';
}
}
}
3、关于单链表的经典面试题
3.1 求单链表中有效节点个数
代码实现：
public static int getLength(LanguageNode head) {
if (head.next == null) {
return 0;
}
LanguageNode tmp = head;
int length = 0;
while (tmp.next != null) {
length++;
tmp = tmp.next;
}
return length;
}
3.2 查找单链表中的倒数第K个节点
解析思路：
编写一个方法同时接收head节点和index节点index表示倒数第index个节点先把链表从头遍历一遍，得到链表的总长度为length,这里可以使用上面的getLength函数得到size后，我们可以从链表的第一个开始遍历（size-index）个，就可以得到如果找到该节点就返回，否则返回null 代码实现：
public static LanguageNode findLastIndexNode(LanguageNode head, int index) {
if (head.next == null) {
return null;
}
int size = getLength(head);
if (index < 0 || index > size) {
return null;
}
LanguageNode tmp = head.next;
for (int i = 0; i < size - index; i++) {
tmp = tmp.next;
}
return tmp;
}
3.3 单链表的反转
实现思路：
先定义一个节点reverseHead = new LanguageNode();从头到尾遍历原来的链表，每个遍历节点，将其取出，并放在新的链表先定义一个节点reverseHead的最前端。原来的链表的head.next = reverseHead.next
代码实现
/**
* 单链表反转
*
* @param head 原始链表
* @return
*/
static void reverseList(LanguageNode head) {
//一个节点不需要转换
if (head.next == null || head.next.next == null) {
return;
}
//定义辅助变量
LanguageNode reverseNode = new LanguageNode(0, "", "");
LanguageNode cur = head.next;
LanguageNode next = null;
while (cur != null) {
//保存当前节点的下一个节点
next = cur.next;
//将cut的下一个节点，指向新链表的最前端
cur.next = reverseNode.next;
//将 cur 连接到新的链表上
reverseNode.next = cur;
cur = next;
}
head.next = reverseNode.next;
}
public static void main(String[] args) {
SingleLinkedList linkedList = new SingleLinkedList();
LanguageNode java = new LanguageNode(1, "java", "超级好用");
LanguageNode python = new LanguageNode(2, "python", "python");
LanguageNode goLang = new LanguageNode(3, "goLang", "goLang");
LanguageNode js = new LanguageNode(4, "js", "js");
LanguageNode php = new LanguageNode(5, "php", "php是世界上最好的语言");
LanguageNode node = new LanguageNode(4, "node", "node");
linkedList.addByOrder(python);
linkedList.addByOrder(java);
linkedList.addByOrder(js);
linkedList.addByOrder(php);
linkedList.addByOrder(goLang);
linkedList.update(node);
System.out.println("反转前链表：");
linkedList.list();
reverseList(linkedList.getHead());
System.out.println("反转后链表：");
linkedList.list();
}
//结果：
反转前链表：
LanguageNode{no=1, language='java', languageDescribe='超级好用'}
LanguageNode{no=2, language='python', languageDescribe='python'}
LanguageNode{no=3, language='goLang', languageDescribe='goLang'}
LanguageNode{no=4, language='node', languageDescribe='node'}
LanguageNode{no=5, language='php', languageDescribe='php是世界上最好的语言'}
反转后链表：
LanguageNode{no=5, language='php', languageDescribe='php是世界上最好的语言'}
LanguageNode{no=4, language='node', languageDescribe='node'}
LanguageNode{no=3, language='goLang', languageDescribe='goLang'}
LanguageNode{no=2, language='python', languageDescribe='python'}
LanguageNode{no=1, language='java', languageDescribe='超级好用'}
从尾到头打印单链表（方法1、反向遍历，2、Stack栈）
实现思路：
方式一
可以先进行链表反转，在进行便利打印，反转会破坏原始链表结构，不推荐使用 方式二
可以利用栈的数据结构，将各个节点压入打栈中，然后利用栈的先进后出的特点，实现逆序打印。
代码实现
static void reversePrint(LanguageNode head) {
if (head.next == null) {
return;
}
Stack<LanguageNode> stack = new Stack<>();
while (head.next != null) {
stack.push(head.next);
head = head.next;
}
while (stack.size() > 0) {
System.out.println(stack.pop());
}
}
public static void main(String[] args) {
SingleLinkedList linkedList = new SingleLinkedList();
LanguageNode java = new LanguageNode(1, "java", "超级好用");
LanguageNode python = new LanguageNode(2, "python", "python");
LanguageNode goLang = new LanguageNode(3, "goLang", "goLang");
LanguageNode js = new LanguageNode(4, "js", "js");
LanguageNode php = new LanguageNode(5, "php", "php是世界上最好的语言");
LanguageNode node = new LanguageNode(4, "node", "node");
linkedList.addByOrder(python);
linkedList.addByOrder(java);
linkedList.addByOrder(js);
linkedList.addByOrder(php);
linkedList.addByOrder(goLang);
linkedList.update(node);
System.out.println("正序打印：");
linkedList.list();
System.out.println("倒叙序打印：");
reversePrint(linkedList.getHead());
}
//输出结果
正序打印：
LanguageNode{no=1, language='java', languageDescribe='超级好用'}
LanguageNode{no=2, language='python', languageDescribe='python'}
LanguageNode{no=3, language='goLang', languageDescribe='goLang'}
LanguageNode{no=4, language='node', languageDescribe='node'}
LanguageNode{no=5, language='php', languageDescribe='php是世界上最好的语言'}
倒叙序打印：
LanguageNode{no=5, language='php', languageDescribe='php是世界上最好的语言'}
LanguageNode{no=4, language='node', languageDescribe='node'}
LanguageNode{no=3, language='goLang', languageDescribe='goLang'}
LanguageNode{no=2, language='python', languageDescribe='python'}
LanguageNode{no=1, language='java', languageDescribe='超级好用'}
