侧边栏壁纸
博主头像
快乐江湖的博客博主等级

更多内容请点击CSDN关注“快乐江湖”

  • 累计撰写 127 篇文章
  • 累计创建 33 个标签
  • 累计收到 2 条评论

目 录CONTENT

文章目录
Java基础教程

第十四章第二节2：Java集合框架之LinkedList

快乐江湖
快乐江湖
2023-03-25 / 0 评论 / 0 点赞 / 18 阅读 / 21252 字

一：双向链表

（1）定义

双链表：双链表在单链表的基础上再增加一个指针域，用于指向它的前驱结点

（2）实现

package myLinkedList;

public class MyLinkedList {
    //结点定义
    static class ListNode{
        public int val;
        public ListNode prev;
        public ListNode next;
        public ListNode(int val){
            this.val = val;
        }
    }

    //头结点和尾节点
    public ListNode head;
    public ListNode tail;

    //显示链表
    public void disPlay(){
        ListNode cur = this.head;
        while(cur != null){
            System.out.print(cur.val + "---");
            cur = cur.next;
        }
        System.out.println();
    }
    //返回某个索引对应的结点
    private ListNode findIndexNode(int index){
        ListNode cur = head;
        while(index != 0){
            cur = cur.next;
            index--;
        }
        return cur;
    }

    //判断某个结点是否在链表中
    public boolean contains(int key){
        ListNode cur = this.head;
        while(cur != null){
            if(cur.val == key){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    //返回链表长度
    public int size(){
        int count = 0;
        ListNode cur = this.head;
        while(cur != null){
            count++;
            cur = cur.next;
        }
        return count;
    }

    //头插法
    public void createHead(int data){
        ListNode node = new ListNode(data);
        if(this.head == null){
            this.head = node;
            this.tail = node;
        }else{
            node.next = this.head;
            this.head.prev = node;
            head = node;
        }
    }

    //尾插法
    public void createTail(int data){
        ListNode node = new ListNode(data);
        if(this.head == null){
            this.head = node;
            this.tail = node;
        }else{
            this.tail.next = node;
            node.prev = this.tail;
            this.tail = node;
        }
    }

    //给定索引插入对应位置
    public void insertByIndex(int index, int data){
        ListNode node = new ListNode(data);
        if(index < 0 || index > this.size()){
            throw  new IndexNotLegalException("非法位置");
        }
        if(index == 0){
            createHead(data);
            return;
        }
        if(index == size()){
            createTail(data);
            return;
        }
        ListNode cur = findIndexNode(index);
        node.next = cur;
        cur.prev.next = node;
        node.prev = cur.prev;
        cur.prev = node;
    }

    //删除第一次出现关键字为key结点
    public void remove(int key){
        ListNode cur = this.head;
        while(cur != null){
            //如果找到就开始删除
            if(cur.val == key){
                //如果删除的第一个元素
                if(cur == this.head){
                    this.head = this.head.next;
                    //防止删除后没有元素导致空指针异常，所以这里要进行判断
                    if(head != null) {
                        this.head.prev = null;
                    }
                }else {
                    cur.prev.next = cur.next;
                    //如果删除的是最后一个结点
                    if(cur.next == null){
                        this.tail =this.tail.prev;
                    }else {
                        cur.next.prev = cur.prev;
                    }
                }
                return;
            }
            cur = cur.next;
        }
    }

    //删除所有关键字为key的结点
    public void removeAll(int key){
        ListNode cur = this.head;
        while(cur != null){
            //如果找到就开始删除
            if(cur.val == key){
                //如果删除的第一个元素
                if(cur == this.head){
                    this.head = this.head.next;
                    //防止删除后没有元素导致空指针异常，所以这里要进行判断
                    if(head != null) {
                        this.head.prev = null;
                    }
                }else {
                    cur.prev.next = cur.next;
                    //如果删除的是最后一个结点
                    if(cur.next == null){
                        this.tail =this.tail.prev;
                    }else {
                        cur.next.prev = cur.prev;
                    }
                }
            }
            cur = cur.next;
        }
    }

    //清空链表
    public void clear(){
        ListNode cur = this.head;
        while(cur != null){
            ListNode curNext = cur.next;
            cur.next = null;
            cur.prev = null;
            cur = curNext;
        }
        this.head = null;
        this.tail = null;
    }


}

二：LinkedList

（1）介绍

LinkedList：Java集合框架中，LinkedList就是双链表，它也实现了List接口

（2）使用

A：构造方法

LinkedList构造方法：如下

  • LinkedList()：无参构造
  • public LinkedLIst(Collection<? extends E> c)：使用其他集合容器中元素构造
public class TestDemo {
    public static void main(String[] args) {
        //构造空的LinkedList
        List<Integer> list1 = new LinkedList<>();
        List<String> list2 = new LinkedList<>();

        //也可以使用ArrayList来构造LinkedList，此时顺序表将会被转换为对应的链式结构
        List<Integer> list3 = new ArrayList<>();
        list3.add(199);
        list3.add(299);
        list3.add(399);
        System.out.println(list3);
        List<Integer> list4 = new LinkedList<>(list3);
        System.out.println(list4);
    }
}

B：常见操作

LinkedList常见操作：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(Object o )：判断o是否在其中
  • int indexOf(Object o)：返回第一个o所在下标
  • int lastIndexOf(Object o)：返回最后一个o的下标
  • List<E> subList(int fromIndex, int toIndex)：截取部分List

下面是一个测试例子，涵盖上面的方法

package testLinkedList;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class TestDemo {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        list.add(6);
        list.add(7);
        System.out.println("list初始情况：" + list);

        list.add(0, 0);
        System.out.println("在起始位置插入元素0：" + list);

        list.removeFirst();//和list.remove()等价
        list.removeLast();
        System.out.println("删除第一个元素和最后一个元素：" + list);

        list.remove(3);
        System.out.println("删除index为3处的元素：" + list);

        System.out.println("检测元素5是否存在：" + list.contains(5));

        System.out.println("从前往后找到元素2的位置" + list.indexOf(2));

        System.out.println("获取index为1处的元素：" + list.get(1));

        list.set(1, 99);
        System.out.println("将index为1处的元素设置为99：" + list);

        List<Integer> sub = list.subList(1, 4);
        System.out.println("截取区间[1, 4)中元素并返回为一个新的LinkedList：" + sub);

        list.clear();
        System.out.println("清空list：" + list);
    }
}

C：LinkedList遍历

①：使用for循环遍历

public class TestDemo {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        list.add(11);
        list.add(22);
        list.add(33);
        list.add(44);
        list.add(55);
        list.add(66);
        list.add(77);

        for(int i = 0; i < list.size(); i++){
            System.out.print(list.get(i) + "-");
        }
        System.out.println();
    }
}

②：使用foreach循环遍历

for(int e:list){
    System.out.println(e + " ");
}
System.out.println();

③：使用迭代器

//正向迭代器
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();
    }

三：ArrayList和LinkedList区别

0
Java 集合框架
版权归属： 快乐江湖
本文链接： https://blog.zxdemo.top/archives/Java%E9%9B%86%E5%90%88%E6%A1%86%E6%9E%B6%E4%B9%8BLinkedList
许可协议： 本文使用《署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)》协议授权

评论区