LinkedList是双向链表结构可以适用于任意插入场景下的插入和删除，效率较高，时间复杂度为O(1)。
模拟实现
public class MyLinkedList { static class ListNode{ private int val;//值域 private ListNode prev;//前驱 private ListNode next;//后继 public ListNode(int val) { this.val = val; } } public ListNode head;//双向链表的头节点 public ListNode last;//双向链表的尾节点 }
LinkedList常用方法
//头插法 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()
实现addFirst方法（头插法）
public void addFirst(int data){ ListNode node = new ListNode(data); //如果链表为空 插入的元素就是头节点和尾节点 if (head==null){ head = node; last = node; }else { node.next = head;//使node的后继是现在的头节点 head.prev = node;//使现在的头节点的前驱是node head = node;//让node成为新的头节点 } }
实现addList方法（尾插法）
public void addLast(int data){ ListNode node = new ListNode(data); //和头插一样 if (last==null){ head = node; last = node; }else { last.next = node;//使现在尾节点的后继为node node.prev = last;//使node的前驱为现在的尾节点 last = last.next;//让node成为尾节点 } }
实现size方法（求链表长度）
public int size(){ ListNode cur = head; int count = 0; while (cur!=null){ count++; cur = cur.next; } return count; }
实现addIndex方法（在任意位置插入元素）
public void addIndex(int index,int data){ //插入的位置如果为0 可以使用头插法 if (index==0){ addFirst(data); return; } //如果在最后一个位置插入 可以使用尾插法 if (index==size()){ addLast(data); return; } ListNode node = new ListNode(data); //判断要插入的下标是否合法 if (index<0||index>size()){ System.out.println("index 不合法"+index); return; } ListNode cur = head; //让cur走到要插入的位置 while (index!=0){ cur = cur.next; index--; } node.next = cur; cur.prev.next = node; node.prev = cur.prev; cur.prev = node; }
实现contains方法（查找是否包含关键字key是否在单链表当中）
public boolean contains(int key){ if (head==null){ return false; } ListNode cur = head; while (cur!=null){ if (cur.val==key){ return true; } cur = cur.next; } return false; }
实现remove方法（删除第一次出现关键字为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){ //只有一个头节点 cur.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; } } }
实现removeAllkey（删除所有值为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){ //只有一个头节点 cur.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; } } }
实现clear方法（清除链表）
public void clear(){ ListNode cur = head; while (cur!=null){ ListNode curNew = cur.next; cur.prev=null; cur.next=null; cur = curNew; } head=null; last=null; }
