一、单链表
单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。
在开头插入。在链接列表中插入新节点的最简单位置是开始。
从头开始删除。删除链表中的第一个节点也很容易
在末尾插入。要在链接列表的末尾插入一个节点，我们维护一个指向列表中最后一个节点的链接。
/*** 单链表*/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;}@Overridepublic 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;}@Overridepublic String toString() {return new StringJoiner(", ", DoubleNode.class.getSimpleName() + "[", "]").add("no=" + no).add("name='" + name + "'").toString();}}
