链表：
链表(Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer）。由于不必按顺序存储，链表在插入的时候可以达到O⑴的复杂度，比另一种线性表：顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n）的时间，而顺序表相应的时间复杂度分别是O(logn）和O⑴。
循环链表：
循环链表是与单链表一样，是一种链式的存储结构，所不同的是，循环链表的最后一个结点的指针是指向该循环链表的第一个结点或者表头结点，从而构成一个环形的链。循环链表的运算与单链表的运算基本一致。所不同的有以下几点：
1、在建立一个循环链表时，必须使其最后一个结点的指针指向表头结点，而不是象单链表那样置为NULL。此种情况还使用于在最后一个结点后插入一个新的结点。
2、在判断是否到表尾时，是判断该结点链域的值是否是表头结点，当链域值等于表头指针时，说明已到表尾。而非象单链表那样判断链域值是否为NULL。
双向链表 ：
双向链表其实是单链表的改进。当我们对单链表进行操作时，有时你要对某个结点的直接前驱进行操作时，又必须从表头开始查找。这是由单链表结点的结构所限制的。因为单链表每个结点只有一个存储直接后继结点地址的链域，那么能不能定义一个既有存储直接后继结点地址的链域，又有存储直接前驱结点地址的链域的这样一个双链域结点结构呢？这就是双向链表。在双向链表中，结点除含有数据域外，还有两个链域，一个存储直接后继结点地址，一般称之为右链域；一个存储直接前驱结点地址，一般称之为左链域。
优缺点：
单向链表：
优点：单向链表增加删除节点简单。遍历时候不会死循环。（双向也不会死循环，循环链表忘了进行控制的话很容易进入死循环）
缺点：只能从头到尾遍历。只能找到后继，无法找到前驱，也就是只能前进。
双向链表：
优点：可以找到前驱和后继，可进可退。
缺点：增加删除节点复杂（其实就复杂一点点）
实现上的主要区别：
单向链表和双向循环链表最大的不同就是头结点是否是哑元。双向循环链表由于head是哑元，因此取元素从head的下一个结点取。单向链表：head不是哑元，第一次必须取head头结点的元素，因此循环上和双向循环链表不同。也就是第一次get并没有进入for循环，直接返回了头结点，从第二次才开始进入for循环，这里要特别注意。
class Link {
static class Node {
//节点值
private Object data;
//下一个节点的引用
private Node next;
public Node(Object data) {
this.data = data;
}
public void add(Node newLink) {
if (this.next == null) {
this.next = newLink; //当前为空则赋值给当前
} else {
this.next.add(newLink); //否则判断下一个节点可以赋值
}
}
public void print() {
if (this.next != null) {
System.out.print(this.data + "-->"); //单向链表最后一个为null
this.next.print();
} else {
System.out.println(this.data);
}
}
public boolean search(Object data) {
if (this.data.equals(data)) {
return true;
}
if (this.next != null) {
return this.next.search(data);
} else {
return false;
}
}
public void del(Node previous, Object data) {
if (this.data.equals(data)) {
previous.next = this.next; //删除即将上一个节点的引用改为当前节点的下一个节点
} else {
if (this.next != null) {
this.next.del(this, data);
}
}
}
}
private Node root;
private int size = 0;
public void addNode(Object data) {
Node newNode = new Node(data);
if (this.root == null) {
this.root = newNode;
} else {
this.root.add(newNode);
}
size++; //容量
}
public int getSize() {
return size;
}
public void print() {
if (root != null) {
this.root.print();
}
}
public boolean searchNode(Object data) {
return this.root.search(data);
}
public void delNode(Object data) {
if (root.data.equals(data)) {
if (root.data != null) {
root = root.next;
} else {
root = null;
}
} else {
root.next.del(root, data);
}
}
}
class CycleLink<T> {
private Node<T> head;
private int size;
static class Node<T> {
private Node<T> next;
private T data;
public Node() {
}
public Node(T data) {
this.data = data;
}
}
public CycleLink(T data) {
head = new Node<>();
head.data = data;
head.next = head;
}
public void addNode(T data) {
Node newNode = new Node(data);
if (head == head.next) {
head.next = newNode;
newNode.next = head;
} else {
Node tmp = head.next;
while (tmp.next != head) {
tmp = tmp.next;
}
tmp.next = newNode;
newNode.next = head;
size++;
}
}
public int getSize() {
return size;
}
public boolean find(T data) {
Node current = head;
while (current.next != head) {
if (current.data.equals(data)) {
return true;
}
current = current.next;
}
return false;
}
public void del(T data) {
Node current = head;
while (current.next != head) {
if (current.data.equals(data)) {
current.data = current.next.data;
current.next = current.next.next;
}
current = current.next;
}
}
public void print() {
Node node = head;
while (node.next != head) {
System.out.print(node.data + " ");
node = node.next;
}
System.out.println();
}
}
class DoubleLink<T> {
private class Node<T> {
private Node<T> pre, next;
private T data;
public Node(T data, Node<T> pre, Node<T> next) {
this.data = data;
this.pre = pre;
this.next = next;
}
public Node() {
this.data = null;
this.pre = null;
this.next = null;
}
}
private int size;
private Node<T> Header;
private Node<T> Tail;
public DoubleLink() {
this.size = 0;
Header = new Node<>(null, null, null);
Tail = new Node<>(null, Header, null);
Header.next = Tail;
}
public void add(T data) {
Node<T> newNode = new Node<T>(data, null, null);
Tail.pre.next = newNode;
newNode.pre = Tail.pre;
newNode.next = Tail;
Tail.pre = newNode;
size++;
}
public boolean isEmpty() {
if (this.size == 0) {
return true;
} else {
return false;
}
}
public int size() {
return this.size;
}
public T getItem(int index) {
if (index > size - 1 || index < 0) {
throw new IndexOutOfBoundsException();
}
Node<T> current = new Node<>();
if (index <= size / 2) {
current = Header.next;
System.out.print("从前查找");
for (int i = 0; i < index; i++) {
current = current.next;
}
} else {
current = Tail.pre;
System.out.print("从后查找");
for (int i = size - 1; i > index; i--) {
current = current.pre;
}
}
return current.data;
}
public void del(T data) {
Node<T> current = Header.next;
while (current.next != null) {
if (current.data.equals(data)) {
current.pre.next = current.next;
current.next.pre = current.pre;
}
current = current.next;
}
}
public void print() {
Node<T> current = Header.next;
while (current.next != null) {
System.out.print(current.data.toString() + " ");
current = current.next;
}
}
}
public class 双向链表 {
public static void main(String[] args) {
//单链表 一根筋 需要的时候只能从头遍历到尾
System.out.println("单链表:");
Link link = new Link();
link.addNode("A");
link.addNode("B");
link.addNode("C");
link.addNode("D");
link.print();
System.out.println("总节点数:" + link.getSize() + " 查找节点：A");
String result = link.searchNode("A") ? "找到!" : "没找到!";
System.out.println("查找结果：" + result);
System.out.println("删除节点A后：");
link.delNode("A");
link.print();
System.out.println();
//循环单链表 从任一结点出发都可访问到链表中每一个元素
System.out.println("循环单链表:");
CycleLink cycleLink = new CycleLink("A");
cycleLink.addNode("B");
cycleLink.addNode("C");
cycleLink.addNode("D");
cycleLink.addNode("E");
cycleLink.print();
System.out.println("长度为：" + cycleLink.getSize());
System.out.println("删除A节点");
cycleLink.del("A");
cycleLink.print();
System.out.println("查找节点B：" + cycleLink.find("B"));
System.out.println();
//双向链表 优势双向，可以访问前驱
System.out.println("双向链表:");
DoubleLink doubleLink = new DoubleLink();
doubleLink.add("A");
doubleLink.add("B");
doubleLink.add("C");
doubleLink.add("D");
doubleLink.add("E");
doubleLink.add("F");
doubleLink.print();
System.out.println("第三个元素：" + doubleLink.getItem(2));
System.out.println("第四个元素：" + doubleLink.getItem(5));
System.out.println("isEmpty?" + doubleLink.isEmpty());
System.out.println("size:" + doubleLink.size());
System.out.println("删除节点E");
doubleLink.del("E");
doubleLink.print();
}
}实现方式有所不同，但是原理相同，有点粗糙，有问题请指出，感激不尽。
本站由以下主机服务商提供服务支持：
0条评论