鏈表定義
鏈表是一種物理存儲單元上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯是通過鏈表種的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列節(jié)點組成，每個節(jié)點包括兩部分：一個是存儲數(shù)據(jù)元素的數(shù)據(jù)域，一個是存儲下一個節(jié)點地址的指針域。單向鏈表從頭節(jié)點（也可以沒有頭節(jié)點）開始，指針指向下一個節(jié)點的位置，只能由上一個節(jié)點指向后面節(jié)點，后面節(jié)點不能指向前面節(jié)點。單向鏈表示意圖：
節(jié)點結(jié)構(gòu)
節(jié)點包含了數(shù)據(jù)域和指針域。數(shù)據(jù)域存放該節(jié)點存放的數(shù)據(jù)信息，指針域存放下一個節(jié)點的存儲地址。no、nickName、name為該節(jié)點的數(shù)據(jù)內(nèi)容，nextNode為下一個節(jié)點。
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 + '\'' +
'}';
}
}
鏈表操作
初始化單向鏈表
初始化鏈表的頭節(jié)點，頭節(jié)點數(shù)據(jù)域為空，指針域為下一個節(jié)點的位置。
private Node head = new Node(0, "", "");
遍歷鏈表
因為單向鏈表的頭節(jié)點不能移動，所以借助一個臨時節(jié)點變量進(jìn)行遍歷。
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();
}
}
插入元素
該方法只是將新的節(jié)點放到節(jié)點的末尾去，并不考慮順序等因素。
public void addNode(Node node) {
// 因為head是不能動的，所以需要借助一個臨時變量
Node temp = head;
while (true) {
if (temp.getNextNode() == null) {
break;
}
temp = temp.getNextNode();
}
temp.setNextNode(node);
}
該方法將新的節(jié)點放到節(jié)點中去，考慮節(jié)點的順序（以節(jié)點的 no 屬性為順序）。
public void addSortNode(Node node) {
Node temp = head;
boolean isExist = false;
while (true) {
if (temp.getNextNode() == null) {
break;
}
// 對應(yīng)的序號已經(jīng)存在
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);
}
}
更新節(jié)點
更新某一個節(jié)點的數(shù)據(jù)域內(nèi)容
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("沒有找到對應(yīng)的節(jié)點");
} else {
temp.setName(node.getName());
temp.setNickName(node.getNickName());
}
}
刪除節(jié)點
找到要刪除節(jié)點的上一個節(jié)點，將該節(jié)點的指針域設(shè)置成要刪除節(jié)點的下一個節(jié)點，這樣要刪除的節(jié)點就沒有指針指向了，就會被GC回收，達(dá)到刪除節(jié)點的目的。
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("未找到節(jié)點");
return;
}
temp.setNextNode(temp.getNextNode().getNextNode());
}
有效節(jié)點的個數(shù)
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;
}
倒數(shù){}個節(jié)點
因為單向鏈表的后一個節(jié)點是無法獲取到前一個節(jié)點的位置的，所以我們先計算出該鏈表的有效節(jié)點個數(shù)，再用有效節(jié)點個數(shù) - 倒數(shù)的節(jié)點個數(shù)就是正數(shù)的節(jié)點個數(shù)，這樣可以達(dá)到同樣的效果。
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;
}
// 因為鏈表是單向的，只能從前往后找，倒數(shù)第幾個=總數(shù)-倒數(shù)的數(shù)
if (indexPosition == (count - index)) {
return temp;
}
indexPosition++;
temp = temp.getNextNode();
}
return null;
}
鏈表反轉(zhuǎn)
遍歷舊鏈表，第一個節(jié)點放入新鏈表的第一個節(jié)點，第二個節(jié)點的下一個節(jié)點設(shè)置成新鏈表的第一個節(jié)點，以此類推，舊鏈表的第一個就成了新鏈表的最后一個節(jié)點，第二個節(jié)點就成了新鏈表的倒數(shù)第二個節(jié)點...文章來源：http://www.zghlxwxcb.cn/news/detail-618693.html
public void getReverseList(Node head) {
// 如果當(dāng)前鏈表為空，或者只有一個節(jié)點，無需反轉(zhuǎn)，直接返回
if (head.getNextNode() == null || head.getNextNode().getNextNode() == null) {
return;
}
// 定義一個輔助變量，幫助遍歷原來的鏈表
Node cur = head.getNextNode();
// 指向當(dāng)前節(jié)點cur的下一個節(jié)點
Node next = null;
Node reverseHead = new Node(0, "", "");
// 遍歷原來的鏈表，每遍歷一個節(jié)點，就將其取出，并放在新的鏈表reverseHead的最前端
while (cur != null) {
// 先暫時保存當(dāng)前節(jié)點的下一個節(jié)點，因為后面需要使用
next = cur.getNextNode();
// 將cur的下一個節(jié)點指向新的鏈表的最前端
cur.setNextNode(reverseHead.getNextNode());
reverseHead.setNextNode(cur);
// 讓cur后移
cur = next;
}
// 將head.next 指向reverseHead.next，實現(xiàn)單鏈表的反轉(zhuǎn)
head.setNextNode(reverseHead.getNextNode());
}
逆序打印
利用棧結(jié)構(gòu)先進(jìn)后出的特點，將遍歷的鏈表節(jié)點依次入棧，再打印棧中的節(jié)點，這樣可以在不改變原來鏈表數(shù)據(jù)的情況下進(jìn)行逆序打印輸出。文章來源地址http://www.zghlxwxcb.cn/news/detail-618693.html
public void reversePrint(Node head) {
if (head.getNextNode() == null) {
return;
}
// 創(chuàng)建一個棧，將各個節(jié)點壓入棧
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());
}
}
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)與算法（三）：單向鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
