Collection与数据结构链表与LinkedList(四):双向无头非循环链表的实现与LinkedList的使用

1. 双向无头非循环链表的实现

在这里插入图片描述
下面我们给出一个接口,接口中的这些方法就是待实现的方法

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

下面实现这些方法:

/*** 双向链表的实现*/
public class MyLinkedList_2 implements ILinkedList_2 {class ListNode{public ListNode pre;//比单向链表多出来的地方,和前一个结点也是连起来的public ListNode next;public int val;public ListNode(int val) {this.val = val;}}public ListNode head;public ListNode last;//有末结点/*** 头插法* @param data*/@Overridepublic void addFirst(int data) {ListNode listNode = new ListNode(data);if (head == null){//注意为空的情况head = listNode;last = listNode;}else{//注意加上else,否则在一开始的时候,listnode.next为head,next就会被置为head//就会永远在头结点处死循环listNode.next = head;head.pre = listNode;head = listNode;}}/*** 尾插法* @param data*/@Overridepublic void addLast(int data) {ListNode listNode = new ListNode(data);if (head == null){head = listNode;last = listNode;}else {listNode.pre = last;last.next = listNode;last = last.next;}}private boolean checkIndex(int index){//检查index是否合法if (index > size() ||index < 0){return false;}return true;}private ListNode findNode(int index) {//找到对应下标的结点ListNode cur = head;int count = 0;while (count != index){count ++;cur = cur.next;}return cur;}/*** 在指定位置插入结点* @param index* @param data*/@Overridepublic void addIndex(int index, int data) {if (!checkIndex(index)){throw new IndexExecption("下标输入有误");}if (index == 0){addFirst(data);return;//记得返回,不然下面的代码也会执行}if (index == size()){addLast(data);return;}ListNode listNode = new ListNode(data);ListNode cur = findNode(index);listNode.next = cur;listNode.pre = cur.pre;cur.pre.next = listNode;cur.pre = listNode;}/*** 查看链表中是否包含指定元素* @param key* @return*/@Overridepublic boolean contains(int key) {if (head == null){return false;}ListNode cur = head;while (cur != null){//先遍历链表if (cur.val == key){return true;//找到相等的值直接返回true}cur = cur.next;}return false;//跳出来就证明已经走到了终点,没找到}/*** 删除第一个值为key的结点* @param key*/@Overridepublic void remove(int key) {ListNode cur = head;while(cur != null){//cur向下遍历if (cur.val == key){//cur找到的清空if (cur == head){//如果cur为头结点head = head.next;//head向后移动if (head != null){head.pre = null;}else {//如果cur为头结点且只有一个结点last = null;//last也置为空}}else {//cur不为头结点if (cur.next != null){//cur为中间结点cur.pre.next = cur.next;cur.next.pre = cur.pre;}else {//cur为尾结点cur.pre.next = null;last = last.pre;}}return;//删完返回}cur = cur.next;//cur向下走}}/*** 删除所有值为key结点* @param key*/@Overridepublic void removeAllKey(int key) {ListNode cur = head;while(cur != null){//cur向下遍历if (cur.val == key){//cur找到的清空if (cur == head){//如果cur为头结点head = head.next;//head向后移动if (head != null){head.pre = null;}else {//如果cur为头结点且只有一个结点last = null;//last也置为空}}else {//cur不为头结点if (cur.next != null){//cur为中间结点cur.pre.next = cur.next;cur.next.pre = cur.pre;}else {//cur为尾结点cur.pre.next = null;last = last.pre;}}//直接把return去掉,删完不返回,继续删}cur = cur.next;//cur向下走}}/*** 计算链表大小* @return*/@Overridepublic int size() {int count = 0;ListNode cur = head;while (cur != null){cur = cur.next;count++;}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 curNext = cur.next;//记录下一个结点cur.next = null;cur.pre = null;//每一个结点的next和pre都置空cur = curNext;}head = null;last = null;//head和last指向的仍然是原来的地址,cur只是修改了节点内的值,//所以head和last需要手动置空}
}

[注意事项]

在头插法和尾插法的过程中,如果该链表为空,在把该链表的头结点和尾结点都指向添加结点之后,记得后面不符合条件的语句用else括起来,否者在头插或尾插之后,还会执行head!=null的代码
在中间插入节点的时候,如果插入的结点为头插或者是尾插的时候,记得返回,否者和上面的一条一样,执行完头插和尾插之后,又会执行中间插入的代码.
删除代码的逻辑较为复杂,我们通过一张图来表示

测试上面实现的方法:

/*** 开始测试*/
public class Test {public static void main(String[] args) {MyLinkedList_2 myLinkedList_2 = new MyLinkedList_2();myLinkedList_2.addFirst(1);myLinkedList_2.addFirst(2);myLinkedList_2.addFirst(3);myLinkedList_2.addFirst(4);myLinkedList_2.display();MyLinkedList_2 myLinkedList_21 = new MyLinkedList_2();myLinkedList_21.addLast(1);myLinkedList_21.addLast(2);myLinkedList_21.addLast(3);myLinkedList_21.addLast(4);myLinkedList_21.display();myLinkedList_21.addIndex(1,34);myLinkedList_21.addIndex(2,45);myLinkedList_21.display();MyLinkedList_2 myLinkedList_22 = new MyLinkedList_2();myLinkedList_22.addIndex(0,1);myLinkedList_22.addIndex(1,2);myLinkedList_22.addIndex(2,3);myLinkedList_22.display();System.out.println(myLinkedList_22.contains(2));System.out.println(myLinkedList_22.contains(4));myLinkedList_21.remove(2);myLinkedList_21.display();MyLinkedList_2 myLinkedList_23 = new MyLinkedList_2();MyLinkedList_2 myLinkedList_24 = new MyLinkedList_2();myLinkedList_23.addFirst(1);myLinkedList_23.remove(1);myLinkedList_23.display();myLinkedList_24.remove(1);MyLinkedList_2 myLinkedList_25 = new MyLinkedList_2();myLinkedList_25.addFirst(2);myLinkedList_25.remove(1);MyLinkedList_2 myLinkedList_26 = new MyLinkedList_2();myLinkedList_26.addFirst(1);myLinkedList_26.addFirst(1);myLinkedList_26.addFirst(1);myLinkedList_26.addFirst(1);myLinkedList_26.addFirst(1);myLinkedList_26.addFirst(2);myLinkedList_26.removeAllKey(1);myLinkedList_26.display();}
}

测试结果:

在这里插入图片描述

2. LinkedList的使用

LinkedList的底层是双向无头非循环链表结构，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来了，因此在在任意位置插入或者删除元素时，不需要搬移元素，效率比较高.

2.1 构造方法

方法	说明
public LinkedList()	无参构造方法
public LinkedList(Collection<? extends E> c)	使用容器中的其他容器来构造,传入的容器中的数据类型必须是E的子类,以便兼容

public class LinkedList1 {public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();list.add(1);list.add(2);list.add(3);List<Integer> list1 = new ArrayList<>();list1.add(1);list1.add(2);list1.add(3);LinkedList<Number> list2 = new LinkedList<>(list1);}
}

2.2 常用方法

方法	说明
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(Object o)	判断 o 是否在线性表中
int indexOf(Object o)	返回第一个 o 所在下标
int lastIndexOf(Object o)	返回最后一个 o 的下标
List subList(int fromIndex, int toIndex)	截取部分 list

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());
}

2.3 LinkedList的遍历

import java.util.*;public class LinkedList1 {public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();list.add(1);list.add(2);list.add(3);System.out.println(list);//通过sout遍历for (int x: list) {//通过for_each遍历System.out.print(x+" ");}ListIterator<Integer> iterator = list.listIterator();while (iterator.hasNext()){//通过迭代器向后遍历System.out.println(iterator.next());}ListIterator<Integer> iterator1 = list.listIterator(list.size());while (iterator1.hasPrevious()){//通过迭代器向前遍历System.out.println(iterator1.previous());}}
}

面试题 ArrayList与LinkedList的区别
从插入,修改,删除,查找这几方面来说

插入:顺序表在插入的时候必须把插入点之后的元素全部后移,而链表不需要
修改:顺序表可以直接根据下标找到要修改的元素,而链表需要遍历
删除:顺序表删除点之后的元素必须向前移动,而链表不需要
查找: 顺序表可以直接根据下标查找,而链表需要遍历