参考博客：https://www.cnblogs.com/sang-bit/p/11609824.html
1、双向链表：也叫双链表，是链表的一种，每个数据结点中都有两个指针，分别指向直接后继和直接前驱
2、单向链表：是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始。
3、循环链表本质也是线性表，它的结点结构与单链表的相同。与单链表不同的是，循环链表的表尾结点link域存储不是NULL，而是存储了指向表头指针first的地址。
这样，只要知道了表中一个结点的地址，就能遍历表中任何其他的结点。
单链表
头结点、头指针和首元结点
头结点：有时，在链表的第一个结点之前会额外增设一个结点，结点的数据域一般不存放数据（有些情况下也可以存放链表的长度等信息），此结点被称为头结点。若头结点的指针域为空（NULL），表明链表是空表。头结点对于链表来说，不是必须的，在处理某些问题时，给链表添加头结点会使问题变得简单。
首元结点：链表中第一个元素所在的结点，它是头结点后边的第一个结点。
头指针：永远指向链表中第一个结点的位置（如果链表有头结点，头指针指向头结点；否则，头指针指向首元结点）。
头结点和头指针的区别：头指针是一个指针，头指针指向链表的头结点或者首元结点；头结点是一个实际存在的结点，它包含有数据域和指针域。两者在程序中的直接体现就是：头指针只声明而没有分配存储空间，头结点进行了声明并分配了一个结点的实际物理内存。
单链表中可以没有头结点，但是不能没有头指针！
头节点的引入能使链表对第一个元素的删除和插入和其他元素相同，不用另外说明，使得代码更加简洁。
//Singlelinkedlist.java 第一个为头节点 public class Singlelinkedlist<AnyType> { class Node<AnyType> { public AnyType data; public Node<AnyType> next; public Node(AnyType data,Node<AnyType> next){ this.data=data; this.next=next; } } //首元节点 private Node<AnyType> first; //指向链表中第一个元素所在的结点 //头指针 private Node<AnyType> head; //指向头节点 //链表长度 int thesize; //初始化链表 public boolean initlist(){ thesize=0; first=new Node<>(null,null); head=new Node<>(null,first); return true; } //判断链表是否为空 public boolean isEmpty(){ return thesize==0; } //获取节点 public Node<AnyType> getNode(int i){ Node<AnyType> renode=head; for(int j=0;j<i;j++){ renode=renode.next; } return renode; } //在头部添加元素
public void addFirst(AnyType a){
Node<AnyType> renode=new Node<>(a,null);
if(thesize!=0){
renode.next = first;//否则最后面多一个NULL节点
}
first = renode;
head.next = first;
thesize++;
}
//在末尾添加元素 public void add(AnyType a){ Node<AnyType> renode=new Node<>(a,null); getNode(thesize).next=renode; if(thesize==0){ first = renode; } thesize++; } //删除i位置节点，并返回删掉的数据 public AnyType remove(int i){ if(i==thesize){ AnyType a=getNode(thesize).data; getNode(thesize-1).next=null; thesize--; return a; } Node<AnyType> prev=getNode(i-1); AnyType a=prev.next.data; prev.next=prev.next.next; thesize--; return a; } //在i位置插入新节点 public void insert(int i,AnyType a){ Node<AnyType> prev=getNode(i-1); Node<AnyType> renode=new Node<>(a,prev.next); prev.next=renode; thesize++; } //获取i位置节点的数据 public AnyType get(int i){ return getNode(i).data; } //为i位置元素重新赋值 public void set(int i,AnyType a){ getNode(i).data=a; } //返回链表节点个数 public int length(){ return thesize; } //清空链表 public void clear(){ initlist(); } //打印链表 public void print(){ for(int i=1;i<thesize;i++){ System.out.print(getNode(i).data+"--"); } System.out.println(getNode(thesize).data); } public static void main(String[] args) { Singlelinkedlist<Integer> l = new Singlelinkedlist(); l.initlist(); for(int i =0;i<3;i++){ l.addFirst(i+1); } l.print(); System.out.println(l.first.data); l.add(10); l.print(); int l_2 = l.get(2); System.out.println("the second element is "+l_2); l.insert(1,15); l.print(); int l_2_ = l.get(2); System.out.println("the second element is "+l_2_); l.remove(2); l.print(); l.remove(1); l.print(); l.remove(3); l.print(); } }
3--2--1
3
3--2--1--10
the second element is 2
15--3--2--1--10
the second element is 3
15--2--1--10
2--1--10
2--1
//Singlelinkedlist.java 没有头节点 public class Singlelinkedlist<AnyType> { class Node<AnyType> { public AnyType data; public Node<AnyType> next; public Node(AnyType data, Node<AnyType> next) { this.data = data; this.next = next; } } // // 首元节点 // private Node<AnyType> first; // 指向链表中第一个元素所在的结点 // 头指针 private Node<AnyType> head; // 指向头节点 // 链表长度 int thesize; // 初始化链表 public boolean initlist() { thesize = 0; head = null; return true; } // 判断链表是否为空 public boolean isEmpty() { return thesize == 0; } // 获取节点 public Node<AnyType> getNode(int i) { Node<AnyType> renode = head; for (int j = 0; j < i; j++) { renode = renode.next; } return renode; } // 在头部添加元素 public void addFirst(AnyType a) { Node<AnyType> renode = new Node<>(a, null); if (thesize == 0) { head = renode; thesize++; return; } renode.next = head; head = renode; thesize++; } // 在末尾添加元素 public void addLast(AnyType a) { Node<AnyType> renode = new Node<>(a, null); if (thesize == 0) { head = renode; thesize++; return; } getNode(thesize - 1).next = renode; thesize++; } // 删除i位置节点，并返回删掉的数据 public AnyType remove(int i) { if (i == 0) { AnyType a = head.data; head = head.next; thesize--; return a; } Node<AnyType> prev = getNode(i - 1); AnyType a = prev.next.data; prev.next = prev.next.next; thesize--; return a; } // 在i位置插入新节点 public void add(int i, AnyType a) { if (i == 0) { addFirst(a); return; } Node<AnyType> prev = getNode(i - 1); Node<AnyType> renode = new Node<>(a, prev.next); prev.next = renode; thesize++; } // 获取i位置节点的数据 public AnyType get(int i) { return getNode(i).data; } // 为i位置元素重新赋值 public void set(int i, AnyType a) { getNode(i).data = a; } // 返回链表节点个数 public int length() { return thesize; } // 清空链表 public void clear() { initlist(); } // 打印链表 public void print() { System.out.println(thesize); for (int i = 0; i < thesize; i++) { System.out.print(getNode(i).data + " "); } System.out.println(); } public static void main(String[] args) { Singlelinkedlist<Integer> l = new Singlelinkedlist<Integer>(); l.initlist(); for (int i = 0; i < 3; i++) { l.addFirst(i + 1); } l.print(); l.addLast(10); l.print(); int l_2 = l.get(2); System.out.println("the second element is " + l_2); l.add(1, 15); l.print(); int l_2_ = l.get(2); System.out.println("the second element is " + l_2_); l.add(0, 115); l.print(); int l_3_ = l.get(2); System.out.println("the second element is " + l_3_); l.add(6, 150); l.print(); int l2_ = l.get(2); System.out.println("the second element is " + l2_); l.remove(0); l.print(); l.remove(1); l.print(); l.remove(0); l.print(); l.remove(1); l.print(); l.remove(2); l.print(); l.remove(1); l.print(); l.remove(0); l.print(); } }
3
3 2 1
4
3 2 1 10
the second element is 1
5
3 15 2 1 10
the second element is 2
6
115 3 15 2 1 10
the second element is 15
7
115 3 15 2 1 10 150
the second element is 15
6
3 15 2 1 10 150
5
3 2 1 10 150
4
2 1 10 150
3
2 10 150
2
2 10
1
2
0
插入
import java.util.*; import javax.swing.plaf.metal.MetalRadioButtonUI; public class Main { static class Node { int val; Node next; public Node(int val) { this.val = val; } } static Node head; public void addfirst(int val) { Node node = new Node(val); if (head == null) { head = node; return; } node.next = head; head = node; } public void addlast(int val) { Node px = head; Node node = new Node(val); if (head == null) { head = node; return; } while (px.next != null) { px = px.next; } px.next = node; } public void printl(Node p) { Node px = p; while (px != null) { System.out.println(px.val + " "); px = px.next; } System.out.println(" "); } public static void main(String[] args) { Main ma = new Main(); // ma.addlast(1); // ma.addlast(7); // ma.addlast(10); // ma.addlast(19); // ma.printl(head);//1 7 10 19 ma.addfirst(1); ma.addfirst(7); ma.addfirst(10); ma.addfirst(19); ma.printl(head);// 19 10 7 1 } }
import java.util.*; import javax.swing.plaf.metal.MetalRadioButtonUI; public class Main { static class Node { int val; Node next; public Node() { } public Node(int val) { this.val = val; } } static Node head1, head2; static int cnt1, cnt2; public void init() { head1 = new Node(); head2 = new Node(); } // 包装为函数 插入 public Node addfirst(int val, Node head, int size) { Node tmp = new Node(val); if (size == 0) { head = tmp; return head; } tmp.next = head; head = tmp; return head; } public Node addlast(int val, Node head, int size) { Node tmp = new Node(val); if (size == 0) { head = tmp; return head; } Node p = head; while (p.next != null) { p = p.next; } p.next = tmp; return head; } public void printl(Node p) { Node px = p; while (px != null) { System.out.println(px.val + " "); px = px.next; } System.out.println(" "); } public static void main(String[] args) { Main ma = new Main(); ma.init(); head1 = ma.addlast(1, head1, cnt1++); head1 = ma.addfirst(4, head1, cnt1++); head1 = ma.addfirst(10, head1, cnt1++); head1 = ma.addlast(7, head1, cnt1++); ma.printl(head1); head2 = ma.addfirst(2, head2, cnt2++); head2 = ma.addlast(3, head2, cnt2++); head2 = ma.addfirst(8, head2, cnt2++); head2 = ma.addlast(10, head2, cnt2++); ma.printl(head2); System.out.println(cnt1 + " " + cnt2); } }
10
4
1
7
8
2
3
10
4 4