1、什么是链表？
链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。
通俗点，就是每个元素是一个节点，然后用一个指针域给后面的节点连起来，第一个节点没有前驱，最后一个节点没有后继。
实际中要实现的链表的结构非常多样，以下情况组合起来就有8种链表结构：
1. 单向、双向 2. 带头、不带头 3. 循环、非循环
我们重点讲解单向非循环链表和双向非循环链表，同时这两个也是笔试中考的比较多的。
2、实现一个单向非循环链表
2.1 实现前的约定
因为链表的每个元素是一个节点，所以我们采取内部类的方式，而我们还需要定义一个头节点的引用，来始终指向头节点。
public class MySingleList { private ListNode head; //引用头节点 // 链表每个元素是一个节点 private class ListNode { private int val; //存放数据元素 private ListNode next; //存放下一个节点地址 //构造方法 public ListNode(int val) { this.val = val; } } }
注意：链表最少有两个域，分别是数据域和指针域，当然你也可以有多个数据域和指针域。
我们还需要实现以下几个常用的方法：
public void addFirst(int data); //头插法 public void addLast(int data); //尾插法 public boolean addIndex(int index,int data); //任意位置插入,第一个数据节点为0号下标 public boolean contains(int key); //查找关键字key是否在单链表当中 public void remove(int key); //删除第一次出现关键字为key的节点 public void removeAllKey(int key); //删除所有值为key的节点 public int size(); //得到单链表的长度 public void clear(); //清空链表
2.2 addFirst 方法
public void addFirst(int data) { ListNode newNode = new ListNode(data); //把传过来的值放到新的节点中 newNode.next = this.head; //新节点的next指向头节点 this.head = newNode; //使新节点成为头节点 }
因为head默认是指向空的，当链表为null，也不影响这个代码的执行，不信你下来画画图咯。
2.3 addList 方法
public void addLast(int data) { ListNode newNode = new ListNode(data); // 如果链表为空的情况 if (this.head == null) { this.head = newNode; return; } // 先找到最后一个节点 ListNode cur = this.head; while (cur.next != null) { cur = cur.next; } cur.next = newNode; }
2.4 addIndex 方法
//任意位置插入,第一个数据节点为0号下标 private ListNode findIndexPrevNode(int index) { ListNode cur = this.head; while (index - 1 != 0) { cur = cur.next; index--; } return cur; } public boolean addIndex(int index,int data) { // 判断index下标的有效性 if (index < 0 || index > size()) { return false; } // 如果在0下标插入则是头插 if (index == 0) { addFirst(data); //头插 return true; } // 如果在末尾插入则是尾插 if (index == size()) { addLast(data); //尾插 return true; } ListNode newNode = new ListNode(data); //新节点 // 在中间插入 ListNode prevNode = findIndexPrevNode(index); //找到index下标的前一个节点 newNode.next = prevNode.next; //新节点的next被改为index的位置的节点 prevNode.next = newNode; //index位置前一个节点next被改成新节点 return true; }
这个代码我们首先需要找到index下标的前一个节点，先让新节点跟index位置的节点绑定起来，在把index的前一个节点与新节点连起来，这个地方说文字是不清楚的，小伙伴们可以下来按照我这个代码画图就能理解了，也可也直接看博主之前的C语言实现数据结构专栏，那里面有图解哈。
2.5 contains 方法
//查找关键字key是否在单链表当中 public boolean contains(int key) { // 当链表为空的情况 if (this.head == null) { return false; } ListNode cur = this.head; // 遍历列表 while (cur != null) { if (cur.val == key) { return true; //找到了返回true } cur = cur.next; } return false; //找不到返回false }
思路很简单，遍历一遍链表，找到 cur 为空位置，如果有返回true，没有返回false，交给小伙伴自己下来画图咯。
2.6 remove 方法
//删除第一次出现关键字为key的节点 public void remove(int key) { if (this.head == null) { return; } ListNode cur = this.head; // 如果删除的是key为头节点 if (this.head.val == key) { this.head = head.next; return; } // 这里不能是cur!=null, 不然会越界！！！ while (cur.next != null) { // 找到 key 的前一个节点 if (cur.next.val == key) { //当前的cur为key的前一个节点 cur.next = cur.next.next; //cur链接到key的后一个节点 return; } cur = cur.next; } }
这里我们需要找到key的前一个节点，然后进行跟key后面的节点绑定即可，当key对应节点没人引用了，则会被自动回收掉。
2.7 removeAllKey 方法
//删除所有值为key的节点 public void removeAllKey(int key) { if (this.head == null) { return; } // 采用前后指针的方法 ListNode cur = this.head; ListNode prev = this.head; while (cur != null) { if (cur.val == key) { prev.next = cur.next; //跳过key节点指向下一个节点 } else { prev = cur; } cur = cur.next; } // 判断第一个节点是不是key if (this.head.val == key) { this.head = this.head.next; //head指向下一个节点 } }
这里大家伙先自己看看，后面讲解OJ题会有这道题详解的。
2.8 size 和 clear 方法
我相信这两个方法就不需要多说了吧？遍历？直接头指针置null？这不就简单了吗，这里就不写了哈，交给各位了！
