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
     */
    @Override
    public 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
     */
    @Override
    public 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
     */
    @Override
    public 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
     */
    @Override
    public 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
     */
    @Override
    public 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
     */
    @Override
    public 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
     */
    @Override
    public int size() {
        int count = 0;
        ListNode cur = head;
        while (cur != null){
            cur = cur.next;
            count++;
        }
        return count;
    }

    /**
     * 打印链表
     */
    @Override
    public void display() {
        ListNode cur = head;
        while (cur != null){
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }

    /**
     * 清空链表
     */
    @Override
    public 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);
	// 在起始位置插入0
	list.add(0, 0); // add(index, elem): 在index位置插入元素elem
	System.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，否则返回false
	if(!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位置的元素设置为elem
	System.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 {

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

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

2. LinkedList的使用

2.1 构造方法

2.2 常用方法

2.3 LinkedList的遍历

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