链表定义
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑是通过链表种的指针链接次序实现的。链表由一系列节点组成，每个节点包括两部分：一个是存储数据元素的数据域，一个是存储下一个节点地址的指针域。单向链表从头节点（也可以没有头节点）开始，指针指向下一个节点的位置，只能由上一个节点指向后面节点，后面节点不能指向前面节点。单向链表示意图：
节点结构
节点包含了数据域和指针域。数据域存放该节点存放的数据信息，指针域存放下一个节点的存储地址。no、nickName、name为该节点的数据内容，nextNode为下一个节点。
public class Node {
private Integer no;
private String name;
private String nickName;
private Node nextNode;
public Node(int no, String name, String nickName) {
this.no = no;
this.name = name;
this.nickName = nickName;
}
@Override
public String toString() {
return "Node{" +
"no=" + no +
", name='" + name + ''' +
", nickName='" + nickName + ''' +
'}';
}
}
链表操作
初始化单向链表
初始化链表的头节点，头节点数据域为空，指针域为下一个节点的位置。
private Node head = new Node(0, "", "");
遍历链表
因为单向链表的头节点不能移动，所以借助一个临时节点变量进行遍历。
public void showLinkList() {
if (head.getNextNode() == null) {
System.out.println("链表为空");
return;
}
Node temp = head.getNextNode();
while (true) {
if (temp == null) {
break;
}
System.out.println(temp);
temp = temp.getNextNode();
}
}
插入元素
该方法只是将新的节点放到节点的末尾去，并不考虑顺序等因素。
public void addNode(Node node) {
// 因为head是不能动的，所以需要借助一个临时变量
Node temp = head;
while (true) {
if (temp.getNextNode() == null) {
break;
}
temp = temp.getNextNode();
}
temp.setNextNode(node);
}
该方法将新的节点放到节点中去，考虑节点的顺序（以节点的 no 属性为顺序）。
public void addSortNode(Node node) {
Node temp = head;
boolean isExist = false;
while (true) {
if (temp.getNextNode() == null) {
break;
}
// 对应的序号已经存在
if (temp.getNo().equals(node.getNo())) {
isExist = true;
break;
}
if (temp.getNextNode().getNo() > node.getNo()) {
break;
}
temp = temp.getNextNode();
}
if (isExist) {
System.out.println("插入的序号 " + node.getNo() + " 已存在");
} else {
node.setNextNode(temp.getNextNode());
temp.setNextNode(node);
}
}
更新节点
更新某一个节点的数据域内容
public void updateNode(Node node) {
if (head.getName().equals("")) {
System.out.println("链表为空");
}
Node temp = head.getNextNode();
while (true) {
if (temp == null) {
break;
}
if (temp.getNo() == node.getNo()) {
break;
}
temp = temp.getNextNode();
}
if (temp == null || temp.getNo() != node.getNo()) {
System.out.println("没有找到对应的节点");
} else {
temp.setName(node.getName());
temp.setNickName(node.getNickName());
}
}
删除节点
找到要删除节点的上一个节点，将该节点的指针域设置成要删除节点的下一个节点，这样要删除的节点就没有指针指向了，就会被GC回收，达到删除节点的目的。
public void deleteNode(Integer no) {
if (head.getNextNode() == null) {
System.out.println("链表为空");
}
Node temp = head;
while (true) {
if (temp.getNextNode() == null) {
break;
}
if (temp.getNextNode().getNo() == no) {
break;
}
temp = temp.getNextNode();
}
if (temp.getNextNode() == null) {
System.out.println("未找到节点");
return;
}
temp.setNextNode(temp.getNextNode().getNextNode());
}
有效节点的个数
public Integer getListNodeConunt() {
if (head.getNextNode() == null) {
return 0;
}
Node temp = head.getNextNode();
Integer count = 0;
while (true) {
if (temp == null) {
break;
}
count++;
temp = temp.getNextNode();
}
return count;
}
倒数{}个节点
因为单向链表的后一个节点是无法获取到前一个节点的位置的，所以我们先计算出该链表的有效节点个数，再用有效节点个数 - 倒数的节点个数就是正数的节点个数，这样可以达到同样的效果。
public Node getLastNode(SingleLinkList list, Integer index) {
Integer count = list.getListNodeConunt();
if (Optional.of(list).isEmpty()) {
return null;
}
// 第几个元素
Integer indexPosition = 0;
Node temp = head.getNextNode();
while (true) {
if (temp == null) {
break;
}
// 因为链表是单向的，只能从前往后找，倒数第几个=总数-倒数的数
if (indexPosition == (count - index)) {
return temp;
}
indexPosition++;
temp = temp.getNextNode();
}
return null;
}
链表反转
遍历旧链表，第一个节点放入新链表的第一个节点，第二个节点的下一个节点设置成新链表的第一个节点，以此类推，旧链表的第一个就成了新链表的最后一个节点，第二个节点就成了新链表的倒数第二个节点...
public void getReverseList(Node head) {
// 如果当前链表为空，或者只有一个节点，无需反转，直接返回
if (head.getNextNode() == null || head.getNextNode().getNextNode() == null) {
return;
}
// 定义一个辅助变量，帮助遍历原来的链表
Node cur = head.getNextNode();
// 指向当前节点cur的下一个节点
Node next = null;
Node reverseHead = new Node(0, "", "");
// 遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead的最前端
while (cur != null) {
// 先暂时保存当前节点的下一个节点，因为后面需要使用
next = cur.getNextNode();
// 将cur的下一个节点指向新的链表的最前端
cur.setNextNode(reverseHead.getNextNode());
reverseHead.setNextNode(cur);
// 让cur后移
cur = next;
}
// 将head.next 指向reverseHead.next，实现单链表的反转
head.setNextNode(reverseHead.getNextNode());
}
逆序打印
利用栈结构先进后出的特点，将遍历的链表节点依次入栈，再打印栈中的节点，这样可以在不改变原来链表数据的情况下进行逆序打印输出。
public void reversePrint(Node head) {
if (head.getNextNode() == null) {
return;
}
// 创建一个栈，将各个节点压入栈
Stack<Node> stack = new Stack<>();
Node cur = head.getNextNode();
while (cur != null) {
stack.push(cur);
cur = cur.getNextNode();
}
while (stack.size() > 0) {
System.out.println(stack.pop());
}
}
内容来源于网络如有侵权请私信删除
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
