链表介绍
链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。
链表与数组的区别
链表和数组都叫可以叫做线性表，
数组又叫做顺序表，主要区别在于，顺序表是在内存中开辟一段连续的空间来存储数据，而链表是靠指针来连接多块不连续（也可以是连续）的空间，在逻辑上形成一片连续的空间来存储数据。
两种各有各的好处，链表方便删除和插入，顺表表方便排序等。
单线链表
原文链接：JAVA单向链表的操作（增加节点、查找节点、删除节点）
主要实现方法：递归
class Link { //链表类
class Node { //保存每一个节点，此处为了方便直接定义成内部类
private String data; //节点的内容
private Node next; //保存下一个节点
public Node(String data) { //通过构造方法设置节点内容
this.data = data;
}
public void add(Node node) { //增加节点
if (this.next == null) { //如果下一个节点为空，则把新节点加入到next的位置上
this.next = node;
} else { //如果下一个节点不为空，则继续找next
this.next.add(node);
}
}
public void print() { //打印节点
if (this.next != null) {
System.out.print(this.data + "-->");
this.next.print();
} else {
System.out.print(this.data + "\n");
}
}
public boolean search(String data) { //内部搜索节点的方法
if (this.data.equals(data)) {
return true;
}
if (this.next != null) {
return this.next.search(data);
} else {
return false;
}
}
public void delete(Node previous, String data) { //内部删除节点的方法
if (this.data.equals(data)) {
previous.next = this.next;
} else {
if (this.next != null) {
this.next.delete(this, data);
}
}
}
}
private Node root; //定义头节点
public void addNode(String data) { //根据内容添加节点
Node newNode = new Node(data); //要插入的节点
if (this.root == null) { //没有头节点，则要插入的节点为头节点
this.root = newNode;
} else { //如果有头节点，则调用节点类的方法自动增加
this.root.add(newNode);
}
}
public void print() { //展示列表的方法
if (root != null) { //当链表存在节点的时候进行展示
this.root.print();
}
}
public boolean searchNode(String data) { //在链表中寻找指定内容的节点
return root.search(data); //调用内部搜索节点的方法
}
public void deleteNode(String data) { //在链表中删除指定内容的节点
if (root.data.equals(data)) { //如果是头节点
if (root.next != null) {
root = root.next;
} else {
root = null;
}
} else {
root.next.delete(this.root, data);
}
}
}
public class LinkDemo {
public static void main(String[] args) {
Link l = new Link();
l.addNode("A");
l.addNode("B");
l.addNode("C");
l.addNode("D");
System.out.println("原链表：");
l.print();
String searchNode = "B";
System.out.println("查找节点:" + searchNode);
String result = l.searchNode(searchNode) ? "找到!" : "没找到!";
System.out.println("查找结果：" + result);
System.out.println("删除节点：" + searchNode);
l.deleteNode(searchNode);
System.out.println("删除节点后的链表：");
l.print();
}
}
双向链表
原文链接： JAVA实现双向链表
主要实现方法：前后节点的替换
class DoubleLinkedList {
// 节点类Node
private static class Node {
Object value;
Node prev = this;
Node next = this;
Node(Object v) {
value = v;
}
public String toString() {
return value.toString();
}
}
private Node head = new Node(null); // 头节点
private int size; // 链表大小
// 以下是接口方法
public boolean addFirst(Object o) {
addAfter(new Node(o), head);
return true;
}
public boolean addLast(Object o) {
addBefore(new Node(o), head);
return true;
}
public boolean add(Object o) {
return addLast(o);
}
public boolean add(int index, Object o) {
addBefore(new Node(o), getNode(index));
return true;
}
public boolean remove(int index) {
removeNode(getNode(index));
return true;
}
public boolean removeFirst() {
removeNode(head.next);
return true;
}
public boolean removeLast() {
removeNode(head.prev);
return true;
}
public Object get(int index) {
return getNode(index).value;
}
public int size() {
return size;
}
public String toString() {
StringBuffer s = new StringBuffer("[");
Node node = head;
for (int i = 0; i < size; i++) {
node = node.next;
if (i > 0)
s.append(", ");
s.append(node.value);
}
s.append("]");
return s.toString();
}
//以下是实现方法
private Node getNode(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException();
Node node = head.next;
for (int i = 0; i < index; i++)
node = node.next;
return node;
}
private void addBefore(Node newNode, Node node) {
newNode.next = node;
newNode.prev = node.prev;
newNode.next.prev = newNode;
newNode.prev.next = newNode;
size++;
}
private void addAfter(Node newNode, Node node) {
newNode.prev = node;
newNode.next = node.next;
newNode.next.prev = newNode;
newNode.prev.next = newNode;
size++;
}
private void removeNode(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
node.prev = null;
node.next = null;
size--;
}
}
//有些地方还可以优化，比如查找时可以判断索引是否大于size的一半，如果是的话，就从另一头开始迭代。
//可以用这个类测试一下：
public class DLinkDemo {
public static void main(String[] args) {
DoubleLinkedList dll = new DoubleLinkedList();
//添加
dll.add("张曼玉");
dll.add("钟楚红");
dll.add("刘嘉玲");
System.out.println(dll);
//添加到最前
dll.addFirst("林青霞");
System.out.println(dll);
//添加到最后，同添加
dll.addLast("梅艳芳");
System.out.println(dll);
//添加到指定位置
dll.add(4, "王祖贤");
System.out.println(dll);
//移除最前的
dll.removeFirst();
System.out.println(dll);
//移除最后的
dll.removeLast();
System.out.println(dll);
//移除指定位置上的
dll.remove(2);
System.out.println(dll);
//返回指定位置上的元素
System.out.println(dll.get(1));
}
}
输出：
[张曼玉, 钟楚红, 刘嘉玲]
[林青霞, 张曼玉, 钟楚红, 刘嘉玲]
[林青霞, 张曼玉, 钟楚红, 刘嘉玲, 梅艳芳]
[林青霞, 张曼玉, 钟楚红, 刘嘉玲, 王祖贤, 梅艳芳]
[张曼玉, 钟楚红, 刘嘉玲, 王祖贤, 梅艳芳]
[张曼玉, 钟楚红, 刘嘉玲, 王祖贤]
[张曼玉, 钟楚红, 王祖贤]
钟楚红
![树的基本概念(定义、基本术语、性质)[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)