顺序表：物理上逻辑上都连续；
链表：物理上不一定连续，逻辑上一定连续的。

链表的概念及结构

概念：连表示一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是用过链表中的引用链接次序实现的。

8种链表结构：
单项、双向
带头、不带头
循环、非循环

主要的三种链表：
无头单项非循环链表、带头循环单链表、不带头双向循环链表

代码实现

1. 接口定义

package com.github.linked.Impl;public interface ILinked {// 头插法void addFirst(int data);// 尾插法void addLast(int data);// 任意位置插入，第一数据节点为0号下标boolean addIndex(int index, int data);// 查找是否包含关键字 key 在单链表中boolean contains(int key);// 删除第一次出现的关键字为 key 的节点int remove(int key);// 删除所有值为 key 的节点void removeAllKey(int key);// 得到单链表的长度int getLength();// 打印单链表void display();// 清空单链表以防内存泄漏void clear();
}

2. 代码实现接口

package com.github.linked.Impl;public class SingleListed implements ILinked {// 节点类class Node {private int data;private Node next;public Node(int data) {this.data = data;this.next = next;}}private Node head; //头节点public SingleListed() {this.head = head;}/*** 头插法* @param data 要插入的数据*/@Overridepublic void addFirst(int data) {// 1. 拿到一个实体Node node = new Node(data);// 2. 插入// 如果是第一次插入，直接到头节点if (this.head == null) {this.head = node;} else { //不是第一次插入node.next = this.head; // 插入的节点指向头节点this.head = node;      // 更新头节点}}/*** 尾插法* @param data 要插入的数据*/@Overridepublic void addLast(int data) {// 1. 拿到一个实体Node node = new Node(data);Node cur = this.head;// 2. 插入// 如果是第一次插入，直接到头节点if (this.head == null) {this.head = node;} else {// 找尾巴while (cur.next != null) {cur = cur.next;}// 退出上面的循环，cur所执行的位置就是尾节点cur.next = node;}}// 检测 index 该下标是否合法private void checkIndex(int index) {if (index < 0 || index > getLength())throw new IndexOutOfBoundsException("下标不合法！");}// 找到下标为 index-1 位置的节点private Node searchIndex(int index) {checkIndex(index);if (index == 0)return null;int count = 0; // 记录行走的步数Node cur = this.head;while (cur.next != null && count < index-1) {cur = cur.next;count++;}return cur;}/*** 任意位置插入，第一数据节点为 0号下标* @param index 插入的下标* @param data 要插入的数据* @return true*/@Overridepublic boolean addIndex(int index, int data) {Node node = new Node(data);Node cur = searchIndex(index);// 如果链表为空，直接插入到头节点if (cur == null) {node.next = this.head;this.head = node;} else { // 链表不为空，插入到 cur 的位置处node.next = cur.next;  // 将node链接到cur的下一个节点cur.next = node;       // 再将cur链接到node}return true;}/*** 查找是否包含关键字 key 在单链表中* @param key 要查找的关键字* @return 找到key返回true，否则返回false*/@Overridepublic boolean contains(int key) {Node cur = this.head;while (cur != null) {if (cur.data == key) {return true;}cur = cur.next;}return false;}// 找第一次出现的关键字为 key 的节点的前驱private Node searchPre(int key) {// 1. 是不是第一个节点 if(head,data == key)Node pre = this.head;if (pre.data == key) {// 或者 return null;return this.head;}// 2. if(cur.next.data == key)while (pre.next != null) {if (pre.next.data == key) {return pre;}pre = pre.next;}return null;}/*** 删除第一次出现的关键字为 key 的节点* @param key 要删除的关键字* @return oldData*/@Overridepublic int remove(int key) {int oldData = 0;Node pre = searchPre(key);// 1. 若没有找到if (pre == null) {// return -1;throw new UnsupportedOperationException("没有key的前驱");}// 2. 找到了，并且在第一个节点if (pre == this.head && pre.data == key){oldData = this.head.data;this.head = this.head.next;return oldData;}// 3. 找到了，并且不在第一个节点Node delNode = pre.next; // 确定要删除的节点的位置pre.next = delNode.next; // 让要删除的节点的前驱指向要删除的节点的后一个节点，进而删除该节点return 0;}/*** 删除所有值为 key 的节点* @param key 要删除的节点的值*/@Overridepublic void removeAllKey(int key) {Node pre = this.head;Node cur = this.head.next;// 遍历一遍链表while (cur != null) {// 若找到了关键字，进行删除if (cur.data == key) {pre.next = cur.next;cur = cur.next;} else { // 若不是关键字，继续查看链表的下一个pre = cur;cur = cur.next;}if (this.head.data == key) {this.head = this.head.next;}}}/*** 得到单链表的长度* @return 单链表长度*/@Overridepublic int getLength() {Node cur = this.head;int count = 0;  // 节点的个数while (cur != null) {count++;cur = cur.next;}return count;}/*** 打印单链表*/@Overridepublic void display() {Node cur = this.head;while (cur != null) {System.out.print(cur.data + " ");cur = cur.next;}System.out.println();}/*** 清空单链表以防内存泄漏*/@Overridepublic void clear() {while (this.head != null) {Node cur = this.head.next;this.head.next = null;this.head = cur;}}
}

3. 测试代码

package com.github.linked.Impl;public class TestDemo {public static void main(String[] args) {//MySingleListImpl mySingleList = new MySingleListImpl();SingleListed mySingleList = new SingleListed();mySingleList.addFirst(10);mySingleList.addFirst(20);mySingleList.addFirst(30);mySingleList.addFirst(40);mySingleList.addFirst(50);System.out.println("头插：");mySingleList.display();mySingleList.addLast(100);mySingleList.addLast(200);System.out.println("尾插：");mySingleList.display();System.out.println();System.out.print("单链表的长度：");System.out.println(mySingleList.getLength());System.out.println();mySingleList.addIndex(1,15);System.out.println("任意位置插入：");mySingleList.display();System.out.println();System.out.println("查找是否包含关键字 key 在单链表中：");System.out.println("查找关键字125："+mySingleList.contains(125));System.out.println("查找关键字30："+mySingleList.contains(30));System.out.println();System.out.println("删除第一次出现的关键字为 key 的节点：");System.out.println("删除头节点50：");mySingleList.remove(50); //删除头节点mySingleList.display();System.out.println("删除中间节点30：");mySingleList.remove(30); // 删除中间节点mySingleList.display();System.out.println("删除尾节点200：");mySingleList.remove(200); // 删除尾节点mySingleList.display();System.out.println();System.out.println("删除第一次出现的关键字为 key 的节点：");mySingleList.addFirst(20);mySingleList.display();mySingleList.removeAllKey(20);mySingleList.display();System.out.println();System.out.print("单链表的长度：");System.out.println(mySingleList.getLength());System.out.println();// 测试内存泄漏try {Thread.sleep(1000);System.out.println("睡醒了");} catch (InterruptedException e) {e.printStackTrace();}}
}

4. 测试结果