一、單鏈表
單鏈表是一種鏈式存取的資料結構，用一組地址任意的存盤單元存放線性表中的資料元素，鏈表中的資料是以結點來表示的，每個結點的構成：元素(資料元素的映象) + 指標(指示后繼元素存盤位置)，元素就是存盤資料的存盤單元，指標就是連接每個結點的地址資料，
在開頭插入，在鏈接串列中插入新節點的最簡單位置是開始，
從頭開始洗掉，洗掉鏈表中的第一個節點也很容易
在末尾插入，要在鏈接串列的末尾插入一個節點，我們維護一個指向串列中最后一個節點的鏈接，
/**
* 單鏈表
*/
class SingleLinked {
Node HeadNode = new Node(0, "", "");//創建鏈表時頭結點便已經創建完成在
//增加節點
public void add(Node node) {
Node temp = HeadNode;
while (temp.next != null) temp = temp.next;
temp.next = node;
}
/**
* 按no的順序添加節點
*/
public void addNodeByOrder(Node node) {
Node temp = HeadNode;
while (temp.next != null) {//如果沒有大小匹配的，就放在末尾
if (temp.no < node.no && temp.next.no > node.no) break;
}
if (temp.next == null) {
temp.next = node;
} else {
node.next = temp.next;
temp.next = node;
}
}
/**
* 根據no修改資訊
*/
public void updateNodeByNo(Node newNode) {
Node temp = HeadNode;
while (true) {
if (temp.no == newNode.no) {
temp.name = newNode.name;
temp.nickName = newNode.nickName;
break;
}
//最后一個節點
if (temp.next == null) throw new RuntimeException("no錯誤");
temp = temp.next;
}
}
/**
* 洗掉節點
*/
public void deletNodeByNo(int no) {
Node temp = HeadNode;
if (temp.next == null) {
System.out.println("鏈表為空");
return;
}
Node pre = temp;//前驅指標
temp = temp.next;
while (true) {
if (temp.no == no) {
pre.next = temp.next;
break;
}
if (temp.next == null) break;
pre = temp;
temp = temp.next;
}
}
/**
* 遍歷當前鏈表
*/
public void showLinked() {
if (HeadNode.next == null) {
System.out.println("鏈表為空");
return;
}
Node temp = HeadNode.next;
while (true) {
System.out.println(temp);
if (temp.next == null) break;
temp = temp.next;
}
}
}
節點類
/**
* 節點類
*/
class Node {
public int no;//編號
public String name;
public String nickName;
public Node next;//指向下一個節點
//節點的構造方法
public Node(int no, String name, String nickName) {
this.no = no;
this.name = name;
this.nickName = nickName;
this.next = null;
}
@Override
public String toString() {
return new StringJoiner(", ", Node.class.getSimpleName() + "[", "]")
.add("no=" + no)
.add("name='" + name + "'")
.add("nickName='" + nickName + "'")
.toString();
}
}
二、雙向鏈表
雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個資料結點中都有兩個指標，分別指向直接后繼和直接前驅，所以，從雙向鏈表中的任意一個結點開始，都可以很方便地訪問它的前驅結點和后繼結點，一般我們都構造雙向回圈鏈表，
/**
* 鏈表類
*/
class DoublyLinked {
private DoubleNode FirstNode = new DoubleNode(0, "");//創建鏈表時先初始化一個頭結點
/**
* 最后一個節點后
*
* @param node
*/
public void add(DoubleNode node) {
DoubleNode temp = FirstNode;
while (temp.getNext() != null) {
temp = temp.getNext();
}
temp.setNext(node);
node.setPre(temp);
}
/**
* 按順序添加節點
*/
public void addByOrder(DoubleNode node) {
DoubleNode temp = FirstNode;
while (true) {
if (temp.getNo() == node.getNo()) {
System.out.println("節點已經存在");
return;
}
if (temp.getNo() > node.getNo()) {//中間插入
temp.getPre().setNext(node);
node.setPre(temp.getPre());
node.setNext(temp);
temp.setPre(node);
break;
}
if (temp.getNext() == null) {//最后一個節點
temp.setNext(node);
node.setPre(temp);
break;
}
temp = temp.getNext();
}
}
/**
* 遍歷鏈表
*/
public void showLinked() {
if (FirstNode.getNext() == null) {
System.out.println("鏈表為空");
return;
}
DoubleNode temp = FirstNode.getNext();
while (true) {
System.out.println(temp);
if (temp.getNext() == null) break;
temp = temp.getNext();
}
}
/**
* 洗掉節點
*/
public void deleteNode(int no) {
if (FirstNode.getNext() == null) {
System.out.println("鏈表為空");
return;
}
DoubleNode temp = FirstNode.getNext();
while (true) {
if (temp.getNo() == no) {
temp.getPre().setNext(temp.getNext());
temp.getNext().setPre(temp.getPre());
}
if (temp.getNext() == null) break;
temp = temp.getNext();
}
}
/**
* 修改節點資訊
*/
public void updateNode(DoubleNode newNode) {
if (FirstNode.getNext() == null) {
System.out.println("鏈表為空");
return;
}
DoubleNode temp = FirstNode.getNext();
while (true) {
if (temp.getNo() == newNode.getNo()) {
temp.setName(newNode.getName());
break;
}
if (temp.getNext() == null) {
System.out.println("沒有相關節點");
break;
}
temp = temp.getNext();
}
}
}
節點類
/**
* 節點類
*/
class DoubleNode {
private int no;
private String name;
private DoubleNode next;//指向后一個節點
private DoubleNode pre;//指向前一個節點
public DoubleNode(int no, String name) {
this.no = no;
this.name = name;
}
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public DoubleNode getNext() {
return next;
}
public void setNext(DoubleNode next) {
this.next = next;
}
public DoubleNode getPre() {
return pre;
}
public void setPre(DoubleNode pre) {
this.pre = pre;
}
@Override
public String toString() {
return new StringJoiner(", ", DoubleNode.class.getSimpleName() + "[", "]")
.add("no=" + no)
.add("name='" + name + "'")
.toString();
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/245714.html
標籤：其他