编辑文章

描述:

封面图上传：

点击上传图片

## 链表

**链表（Linked list）**是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

在计算机科学中，链表作为一种基础的数据结构可以用来生成其它类型的数据结构。链表通常由一连串节点组成，每个节点包含任意的实例数据（data fields）和一或两个用来指向上一个/或下一个节点的位置的链接（"links"）。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的访问往往要在不同的排列顺序中转换。而链表是一种自我指示数据类型，因为它包含指向另一个相同类型的数据的指针（链接）。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：**单向链表，双向链表以及循环链表**。**引用自**[博客园-月亮编程](https://www.cnblogs.com/mooncode/p/11039266.html)

### 单向链表

单向链表是最简单的链表，它由节点组成，每一个节点，记录了该节点的数据和指向下一个节点的指针，最后一个元素指向为null。如下图：
![单链表](/storage/articles/202004/content/202004012314355e84afdb8a186.png)
代码实现，实例代码为java
```java
  class Node{
  	public String data;//链表的数据先采用简单的String
  	public Node next;//下一个节点
  	public Node(String data){
  		this.data = data;
  	}
  	public void setNext(Node node){
  		this.next = node;
  	}
  	public String getData(){
  		return this.data;
  	}
  	public Node getNext(){
  		return this.next;
  	}
  }
  public class TestLink{
  	public static void main(String[] arg){
  		//定义head
  		Node head = new Node("我是head");
  		Node node1 = new Node("我是node1");
  		Node node2 = new Node("我是node2");
  		Node node3 = new Node("我是node3");
  		head.setNext(node1);//设置head的下一个节点为node1
  		node1.setNext(node2);//设置node1的下一个节点为node2
  		node2.setNext(node3);//设置node2的下一个节点为node3
  		print(head);
  	}
   //递归调用打印链表
  	public static void print(Node head){
       //当最后一个的getNext()返回null,表示链表已经到底了
  		if(head.getNext() == null){
  			return;
  		}
  		System.out.println(head.getData());
  		print(head.getNext());
  	}
  }
  //java TestLink
  //我是head
  //我是node1
  //我是node2
```

### 循环链表

循环链表和单向链表基本相似，也是由节点组成，每一个节点，记录了该节点的数据和指向下一个节点的指针，但不同的是，**它的最后一个节点指向不是null，而是指向第一个元素**。如下图：
![循环链表](/storage/articles/202004/content/202004012315465e84b0221a344.png)
代码实现，实例代码为java

```java
  class Node{
  	public String data;//链表的数据先采用简单的String
  	public Node next;//下一个节点
  	public Node(String data){
  		this.data = data;
  	}
  	public void setNext(Node node){
  		this.next = node;
  	}
  	public String getData(){
  		return this.data;
  	}
  	public Node getNext(){
  		return this.next;
  	}
  }
  public class TestLink{
  	public static void main(String[] arg){
  		//定义head
  		Node head = new Node("我是head");
  		Node node1 = new Node("我是node1");
  		Node node2 = new Node("我是node2");
  		Node node3 = new Node("我是node3");
  		head.setNext(node1);//设置head的下一个节点为node1
  		node1.setNext(node2);//设置node1的下一个节点为node2
  		node2.setNext(node3);//设置node2的下一个节点为node3
          node3.setNext(head);//设置node3的下一个节点为head 此步完成了循环链表
  	}
  }
```

### 双向链表

双向链表也叫双链表。双向链表中不仅有指向后一个节点的指针，还有指向前一个节点的指针。这样便于快速访问前一个节点和后一个节点 如下图：
![双向链表](/storage/articles/202004/content/202004012315025e84aff600aa3.png)
实例代码
```java
  class Node{
  	public String data;//链表的数据先采用简单的String
  	public Node pre;//上一个节点
  	public Node next;//下一个节点
  	public Node(String data){
  		this.data = data;
  	}
  	public void setNext(Node node){
  		this.next = node;
  	}
  	public void setPre(Node node){
  		this.pre = node;
  	}
  	public String getData(){
  		return this.data;
  	}
  	public Node getNext(){
  		return this.next;
  	}
  	public Node getPre(){
  		return this.pre;
  	}
  }
  public class TestLink{
  	public static void main(String[] arg){
  		//定义head
  		Node head = new Node("我是head");
  		Node node1 = new Node("我是node1");
  		Node node2 = new Node("我是node2");
  		Node node3 = new Node("我是node3");
  		head.setNext(node1);//设置head的下一个节点为node1
  		node1.setPre(head);//设置node1的上一个节点为head
  		node1.setNext(node2);//设置node1的下一个节点为node2
  		node2.setPre(node1);//设置node2的上一个节点为node1
  		node2.setNext(node3);//设置node1的下一个节点为node2
  		node3.setPre(node2);//设置node3即最后一个节点的前一个节点为node2
          node3.setNext(head);//设置node3即最后一个节点的下一个节点为head
          head.setPre(node3);//设置head的上一个节点为node3
  	}
  }
  ```