LinkedList 的底层是双向链表结构 ，由于链表没有将元素存储在连续的空间中，元素存储在单独的节 点中，然后通过引用将节点连接起来了，因此在在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。
实现代码：
创建3个类
public class MyLinkedList {//通过内部类来实现static class ListNode {private int val;private ListNode prev;private ListNode next;public ListNode(int val) {this.val = val;}public int getVal() {return val;}public void setVal(int val) {this.val = val;}}public ListNode head;//双链表的头结点public ListNode last;//双链表的尾巴//头插法public void addFirst(int data){ListNode node=new ListNode(data);if(head==null){head=node;last=node;}else {node.next=head;head.prev=node;head=node;}}//尾插法public void addLast(int data){ListNode node=new ListNode(data);if(head==null){head=node;last=node;}else {last.next=node;node.prev=last;last=node;}}//任意位置插入,第一个数据节点为0号下标public void addIndex(int index,int data){checkIndex(index);if(index==0){addFirst(data);}if (index==size()){addLast(data);}ListNode node=new ListNode(data);ListNode cur=searchIndex(index);node.next=cur;cur.prev.next=node;node.prev=cur.prev;cur.prev=node;}//检查数据的合法性public boolean checkIndex(int index){if(index<0||index>size()){throw new IndexOutOFException("index位置不合法！"+index);}return true;}//寻找index的位置private ListNode searchIndex(int index){ListNode cur=head;while (index!=0){cur=cur.next;index--;}return cur;}//查找是否包含关键字key是否在单链表当中public boolean contains(int key){ListNode cur=head;while (cur!=null){if(cur.val==key){return true;}cur=cur.next;}return false;}//删除第一次出现关键字为key的节点public 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 {//删除中间节点和尾巴节点if(cur.next!=null){//删除中间节点cur.prev.next=cur.next;cur.next.prev=cur.prev;}else {//删除尾巴节点cur.prev.next=cur.next;last=last.prev;}}return;}else {cur=cur.next;}}}//删除所有值为key的节点public 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 {last=null;}}else {//删除中间节点和尾巴节点if(cur.next!=null){//删除中间节点cur.prev.next=cur.next;cur.next.prev=cur.prev;}else {//删除尾巴节点cur.prev.next=cur.next;last=last.prev;}}cur=cur.next;}else {cur=cur.next;}}}//得到单链表的长度public int size(){ListNode cur=head;int len=0;while (cur!=null){len++;cur=cur.next;}return len;}public void display(){ListNode cur=head;while (cur!=null){System.out.print(cur.val+" ");cur=cur.next;}}public void clear(){ListNode cur=head;while (cur!=null){ListNode curNext=cur.next;cur.prev=null;cur.next=null;cur=curNext;}head=null;last=null;}
}
2.异常类
public class IndexOutOFException extends RuntimeException{public IndexOutOFException() {}public IndexOutOFException(String message) {super(message);}
}
3.测试类
public class Test {public static void main(String[] args) {MyLinkedList myLinkedList=new MyLinkedList();myLinkedList.addLast(1);myLinkedList.addLast(2);myLinkedList.addLast(3);myLinkedList.addLast(4);//System.out.println(myLinkedList.contains(2));//System.out.println(myLinkedList.size());//myLinkedList.addIndex(2,99);//myLinkedList.remove(2);//myLinkedList.removeAllKey(1);myLinkedList.clear();myLinkedList.display();}
}
使用：
. LinkedList 的其他常用方法介绍
| 方法 | 解释 |
| boolean add (E e) | 尾插 e |
| void add (int index, E element) | 将 e 插入到 index 位置 |
| boolean addAll (Collection<? extends E> c) | 尾插 c 中的元素 |
| E remove (int index) | 删除 index 位置元素 |
| boolean remove (Object o) | 删除遇到的第一个 o |
| E get (int index) | 获取下标 index 位置元素 |
| E set (int index, E element) | 将下标 index 位置元素设置为 element |
| void clear () | 清空 |
| boolean contains int | 判断o是否在线性表中 |
| indexOf(Object o)(Object o) | 返回第一个 o 所在下标 |
| int lastIndexOf(Object o) | 返回最后一个 o 的下标 |
| List<E> subList(int fromIndex, int toIndex) | 截取部分 list |
ArrayList和LinkedList的区别
