使用数组可以存储很多的数据，但是它有固定的长度，不能随意改变它的长度，而链表可以插入和删除大量元素。
接下来我来介绍下单链表
什么是单链表呢？
链表的每个结点中只包含一个指针域，叫做单链表（即构成链表的每个结点只有一个指向直接后继结点的指针，且尾节点的指针为null）。
结点结构如下：
//不带头结点的单链表 public class SingleLinkedListTest { public static void main(String[] args) { SingleLinkedList sll = new SingleLinkedList(); sll.addFirst(21); sll.addFirst(22); sll.addFirst(23); sll.addLast(10); sll.addLast(6); sll.addLast(1); sll.addLast(4); sll.addLast(9); sll.addLast(11); sll.addLast(10); System.out.println("链表的长度是：" + sll.size()); sll.display(); System.out.println(sll.contains(21)); sll.remove(11); sll.display(); sll.removeAllKey(10); sll.display(); } } class SingleLinkedList implements List{ private Node head;//标识一个头结点 //头插法 public void addFirst(int data) { Node node = new Node(data); node.next = head; head = node; } //尾插法 public void addLast(int data) { Node node = new Node(data); if(head == null) { head = node; }else{ Node temp = head; while(temp.next != null) { temp = temp.next; } temp.next = node; } } public boolean checkIndex(int index) { if(index == 0 || index > this.size()) { System.out.println("下标不合法！"); return false; } return true; } //查找是否包含关键字key是否在单链表当中 public boolean contains(int key) { Node temp = head; while(temp != null){ if(temp.data == key) { return true; } temp = temp.next; } return false; } //删除第一次出现关键字为key的节点 public void remove(int key) { if(head == null) { return; } if(head.data == key) { head = head.next; return; } Node temp = head; boolean flag = false; while(temp.next != null) { if(temp.next.data == key) { flag = true; break; } temp = temp.next; } if(flag) {//找到了 Node delNode = temp.next; temp.next = delNode.next; }else{ System.out.println("没有你要找的元素"); } } //删除所有值为key的节点 public void removeAllKey(int key) { if(head.next == null) { return; } if(head.data == key){ head = head.next; } Node prev = head; Node temp = head.next; while(temp != null) { if(temp.data == key) { prev.next = temp.next; temp = temp.next; }else{ prev = temp; temp = temp.next; } } } //得到单链表的长度 public int size() { int size = 0; Node temp = head; while(temp != null) { size++; temp = temp.next; } return size; } public void display() { Node temp = head; while(temp != null) { System.out.printf("%d ", temp.data); temp = temp.next; } System.out.println(); } } class Node { public int data; public Node next;//指向下一个结点 public Node(int data) { this.data = data; } }