一、定义与特点
1.定义：
链表是一种线性数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针（在双向链表中还有指向前一个节点的指针）。
2.特点 ：
1.动态数据结构：可以根据需要动态的增加或删除节点，不需要预先确定大小。
2.内存分配灵活：节点可以分散的存储在内存中，不需要连续的内存空间。
3.插入和删除操作高效：在特定位置插入或删除节点只需要修改几个指针，时间复杂度通常为O（1）（在已知插入或删除位置的情况下）。
二、链表的种类
1.单链表：每个节点只有一个指向下一个节点的指针。
2.双向链表：每个节点有两个指针，分别指向前一个结点和下一个节点。
3.循环链表：单链表或双向链表的一种特殊形式，其中最后一个结点的指针指向链表的第一个节点，形成一个循环。
三、代码示例
这里示例单链表和双向链表的代码
1.单链表
package dataStructure.linked;//链表结点类
public class LinkedNode {int data;//用来指向下一个节点的指针LinkedNode next;//用来在创建节点时给data赋值，由于不知道有没有下一个节点，所以next先不用赋值public LinkedNode(int data) {this.data = data;}
}
package dataStructure.linked;//自定义链表类
public class MyLinkedList {//最简洁的链表，只有头就可以，但是效率会低private LinkedNode head;//有尾节点可以在添加新节点时候直接挂到尾结点的后面，提高效率private LinkedNode tail;//用来记录链表里的数据的数量private int size;public int getSize() {return size;}//用来往链表中添加数据的方法public void add(int e) {//创建节点对象，用来存储数据，然后把节点对象放到链表里LinkedNode node = new LinkedNode(e);//这种情况表示链表是空的if (head == null) {//如果链表是空的，那么新节点即是头节点，又是尾节点head = node;tail = node;} else {//如果链表不为空，则新节点应该添加到尾节点的后面tail.next = node;tail = node;}size++;}//1,2,3,4,5//3public int get(int i) {if (i > size - 1) {throw new IndexOutOfBoundsException("下标越界" + i);}LinkedNode n = head;for (int j = 0; j < i; j++) {n = n.next;}return n.data;}//删除指定位置的数据，并返回被删除数据的值public int delete(int i) {if (i == 0) {LinkedNode n = head;head = head.next;n.next = null;size--;return n.data;}LinkedNode n = head;//要找到被删除节点的前面的节点，所以要循环i-1次for (int j = 0; j < i - 1; j++) {n = n.next;}//先接收一下被删除的节点对象LinkedNode del = n.next;n.next = n.next.next;del.next = null;size--;return del.data;}public String toString() {LinkedNode n = head;String str = "";while (n != null) {str = str + n.data;if (n.next != null) {str = str + "->";}n = n.next;}return str;}public static void main(String[] args) {MyLinkedList linked = new MyLinkedList();linked.add(1);linked.add(2);linked.add(3);linked.add(4);linked.add(5);System.out.println(linked);//1->2->3->4->5linked.delete(2);System.out.println(linked);//1->2->4->5System.out.println(linked.get(3));//5}
}
2.双向链表
package dataStructure.linked;//双向链表的节点类
public class DoubleLinkedNode {int data;//分别用来指向当前节点的后继节点和前驱节点DoubleLinkedNode next;DoubleLinkedNode pre;public DoubleLinkedNode(int data){this.data = data;}
}
package dataStructure.linked;//双向链表类
public class DoubleLinkedList {private DoubleLinkedNode head;private DoubleLinkedNode tail;private int size;public void add(int e) {DoubleLinkedNode n = new DoubleLinkedNode(e);if (head == null) {head = n;tail = n;} else {tail.next = n;n.pre = tail;tail = n;}size++;}//根据下标找到节点对象（注意是找对象，而不是具体数据）private DoubleLinkedNode getNode(int i) {if (i < size / 2) {DoubleLinkedNode n = head;for (int j = 0; j < i; j++) {n = n.next;}return n;} else {DoubleLinkedNode n = tail;for (int j = 0; j < size - i - 1; j++) {n = n.pre;}return n;}}//1,2,3,4,5,6,7,8,9,10public int get(int i) {return getNode(i).data;}public int delete(int i) {if (i == 0) {DoubleLinkedNode n = head;head = head.next;head.pre = null;n.next = null;size--;return n.data;}if (i == size - 1) {DoubleLinkedNode n = tail;tail = tail.pre;tail.next = null;n.pre = null;size--;return n.data;}DoubleLinkedNode n = getNode(i);//把被删除节点的前驱节点，指向被删除节点的后继节点n.pre.next = n.next;//把被删除节点的后继节点的前驱节点，指向被删除节点的前驱节点n.next.pre = n.pre;//断开被删除节点的指向n.pre = null;n.next = null;return n.data;}public String toString() {DoubleLinkedNode n = head;String str = "";while (n != null) {str = str + n.data;if (n.next != null) {str = str + "<=>";}n = n.next;}return str;}public static void main(String[] args) {DoubleLinkedList dll = new DoubleLinkedList();dll.add(1);dll.add(2);dll.add(3);dll.add(4);dll.add(5);System.out.println(dll);//1<=>2<=>3<=>4<=>5dll.delete(1);System.out.println(dll);//1<=>3<=>4<=>5System.out.println(dll.get(3));//4}}