• 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。
• 无头双向非循环链表：在Java的集合框架库中LinkedList底层实现就是无头双向非循环链表。

3. 代码实现

3.1 无头单向非循环链表

3.1.1 节点结构

static class ListNode {public int val;public ListNode next;public ListNode(int val) {this.val = val;}}

3.1.2 方法接口

public interface ISingleLinkedList {
//头插法
public void addFirst(int data);
//尾插法
public void addLast(int data);
//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index,int data);
//查找是否包含关键字key是否在单链表当中
public boolean contains(int key);
//删除第一次出现关键字为key的节点
public void remove(int key);
//删除所有值为key的节点
public void removeAllKey(int key)
//得到单链表的长度
public int size()
//清空链表
public void clear() 
//打印链表
public void display()
}

3.1.3 功能实现

public class MySingleLinkedList implements IMySingleLinkedList {@Overridepublic void addFirst(int data) {ListNode node = new ListNode(data);node.next = head;head = node;}@Overridepublic void addLast(int data) {ListNode node = new ListNode(data);if(head == null) {head = node;return;}ListNode cur = head;while (cur.next != null) {cur = cur.next;}cur.next = node;}@Overridepublic void addIndex(int index,int data) {//1.判断index的合法性try {checkIndex(index);}catch (IndexNotLegalException e) {e.printStackTrace();}//2.index == 0  || index == size()if(index == 0) {addFirst(data);return;}if(index == size()) {addLast(data);return;}//3. 找到index的前一个位置ListNode cur = findIndexSubOne(index);//4. 进行连接ListNode node = new ListNode(val);node.next = cur.next;cur.next = node;}private ListNode findIndexSubOne(int index) {int count = 0;ListNode cur = head;while (count != index-1) {cur = cur.next;count++;}return cur;}private void checkIndex(int index) throws IndexNotLegalException{if(index < 0 || index > size()) {throw new IndexNotLegalException("index不合法");}}@Overridepublic boolean contains(int key) {ListNode cur = head;while (cur != null) {if(cur.val == key) {return true;}cur = cur.next;}return false;}@Overridepublic void remove(int key) {if(head == null) {return;}if(head.val == key) {head = head.next;return;}ListNode cur = head;while (cur.next != null) {if(cur.next.val == key) {ListNode del = cur.next;cur.next = del.next;return;}cur = cur.next;}}@Overridepublic void removeAllKey(int key) {//1. 判空if(this.head == null) {return;}//2. 定义prev 和 curListNode prev = head;ListNode cur = head.next;//3.开始判断并且删除while(cur != null) {if(cur.val == key) {prev.next = cur.next;}else {prev = cur;}cur = cur.next;}//4.处理头节点if(head.val == key) {head = head.next;}}@Overridepublic int size(){int count = 0;ListNode cur = head;while (cur != null) {count++;cur = cur.next;}return count;}@Overridepublic void clear() {//head = null;ListNode cur = head;while (cur != null) {ListNode curN = cur.next;//cur.val = null;cur.next = null;cur = curN;}head = null;}@Overridepublic void display() {ListNode cur = head;while (cur != null) {System.out.print(cur.val+" ");cur = cur.next;}System.out.println();}
}//自定义异常类
public class IndexNotLegalException extends RuntimeException{public IndexNotLegalException() {}public IndexNotLegalException(String msg) {super(msg);}
}

3.2 无头双向非循环链表

3.2.1 节点结构

class ListNode {public int val;public ListNode prev;//前驱public ListNode next;//后继public ListNode(int val) {this.val = val;}}

3.2.2 方法接口

public interface IMyLinkedList {
//头插法
public void addFirst(int data);
//尾插法
public void addLast(int data);
//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index,int data);
//查找是否包含关键字key是否在单链表当中
public boolean contains(int key);
//删除第一次出现关键字为key的节点
public void remove(int key);
//删除所有值为key的节点
public void removeAllKey(int key);
//得到单链表的长度
public int size();
public void display();
public void clear();
}

3.2.3 功能实现

public class MyLinkedList implements IMyLinkedList {public ListNode head;//标志头节点public ListNode last;//标志尾结点//头插法@Overridepublic void addFirst(int data){ListNode node = new ListNode(data);if(head == null) {//是不是第一次插入节点head = last = node;}else {node.next = head;head.prev = node;head = node;}}//尾插法@Overridepublic void addLast(int data){ListNode node = new ListNode(data);if(head == null) {//是不是第一次插入节点head = last = node;}else {last.next = node;node.prev = last;last = last.next;}}//任意位置插入,第一个数据节点为0号下标@Overridepublic void addIndex(int index,int data){try {checkIndex(index);}catch (IndexNotLegalException e) {e.printStackTrace();}if(index == 0) {addFirst(data);return;}if(index == size()) {addLast(data);return;}//1. 找到index位置ListNode cur = findIndex(index);ListNode node = new ListNode(data);//2、开始绑定节点node.next = cur;cur.prev.next = node;node.prev = cur.prev;cur.prev = node;}private ListNode findIndex(int index) {ListNode cur = head;while (index != 0) {cur = cur.next;index--;}return cur;}private void checkIndex(int index) {if(index < 0 || index > size()) {throw new IndexNotLegalException("双向链表插入index位置不合法: "+index);}}//查找是否包含关键字key是否在单链表当中@Overridepublic boolean contains(int key){ListNode cur = head;while (cur != null) {if(cur.val == key) {return true;}cur = cur.next;}return false;}//删除第一次出现关键字为key的节点@Overridepublic void remove(int key){ListNode cur = head;while (cur != null) {if(cur.val == key) {//开始删除 处理头节点if(cur == head) {head = head.next;if(head != null) {head.prev = null;}else {last = null;}}else {cur.prev.next = cur.next;if(cur.next == null) {//处理尾巴节点last = last.prev;}else {cur.next.prev = cur.prev;}}return;//删完一个就走}cur = cur.next;}}//删除所有值为key的节点@Overridepublic void removeAllKey(int key){ListNode cur = head;while (cur != null) {if(cur.val == key) {//开始删除 处理头节点if(cur == head) {head = head.next;if(head != null) {head.prev = null;}else {//head == null 证明只有1个节点last = null;}}else {cur.prev.next = cur.next;if(cur.next == null) {//处理尾巴节点last = last.prev;}else {cur.next.prev = cur.prev;}}}cur = cur.next;}}//得到双向链表的长度@Overridepublic int size(){int count = 0;ListNode cur = head;while (cur != null) {count++;cur = cur.next;}return count;}@Overridepublic void display(){ListNode cur = head;while (cur != null) {System.out.print(cur.val+" ");cur = cur.next;}System.out.println();}@Overridepublic void clear(){ListNode cur = head;while (cur != null) {ListNode curN = cur.next;//cur.val = null;cur.prev = null;cur.next = null;cur = curN;}head = last = null;}
}
//自定义异常类
public class IndexNotLegalException extends RuntimeException{public IndexNotLegalException() {}public IndexNotLegalException(String msg) {super(msg);}
}

4.LinkedList

4.1 概念

public static void main(String[] args) {// 构造一个空的LinkedListList<String> list1 = new LinkedList<>();list1.add("sas");list1.add("asd");list1.add("Jsd");System.out.print("list1: ");for(int i = 0; i < list1.size();i++){System.out.print(list1.get(i)+" ");}System.out.println();System.out.print("list2: ");List<String> list2 = new LinkedList<>(list1);for(int i = 0; i < list2.size();i++){System.out.print(list2.get(i)+" ");}}

public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();list.add(1); // add(elem): 表示尾插list.add(2);list.add(3);list.add(4);list.add(5);list.add(6);list.add(7);System.out.println(list.size());System.out.println(list);// 在起始位置插入0list.add(0, 0); // add(index, elem): 在index位置插入元素elemSystem.out.println(list);list.remove(); // remove(): 删除第一个元素，内部调用的是removeFirst()list.removeFirst(); // removeFirst(): 删除第一个元素list.removeLast(); // removeLast(): 删除最后元素list.remove(1); // remove(index): 删除index位置的元素System.out.println(list);// contains(elem): 检测elem元素是否存在，如果存在返回true，否则返回falseif(!list.contains(1)){list.add(0, 1);}list.add(1);System.out.println(list);System.out.println(list.indexOf(1)); // indexOf(elem): 从前往后找到第一个elem的位置System.out.println(list.lastIndexOf(1)); // lastIndexOf(elem): 从后往前找第一个1的位置int elem = list.get(0); // get(index): 获取指定位置元素list.set(0, 100); // set(index, elem): 将index位置的元素设置为elemSystem.out.println(list);// subList(from, to): 用list中[from, to)之间的元素构造一个新的LinkedList返回List<Integer> copy = list.subList(0, 3);System.out.println(list);System.out.println(copy);list.clear(); // 将list中元素清空System.out.println(list.size());
}

public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();list.add(1); // add(elem): 表示尾插list.add(2);list.add(3);list.add(4);list.add(5);list.add(6);list.add(7);// 使用迭代器遍历---正向遍历ListIterator<Integer> it = list.listIterator();while(it.hasNext()){System.out.print(it.next()+ " ");}System.out.println();
// 使用反向迭代器---反向遍历ListIterator<Integer> rit = list.listIterator(list.size());while (rit.hasPrevious()){System.out.print(rit.previous() +" ");}System.out.println();
}