目录

一、引出链表

二、linkedList的使用

使用方法

linkedList的遍历

三、链表

3.1概念

3.2 无头单向不循环链表

无头单向非循环链表实现

打印链表里面的元素

查找是否包含关键字key是否在单链表当中

得到单链表的长度

头插法

尾插法

任意位置插入,第一个数据节点为0号下标

删除第一次出现关键字为key的节点

删除所有值为key的节点

清空列表

一、引出链表

  在ArrayList任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后搬移，时间复杂度为O(n)，效率比较低，因此ArrayList不适合做任意位置插入和删除比较多的场景。因此：java集合中又引入了linkedList，即链表结构。

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

二、linkedList的使用

使用方法

linkedList list = new linkedList<>(); 
list.add(1); 
// add(elem): 表示尾插

list.add(0, 0); 
// add(index, elem): 在index位置插入元素elem

list.remove(); 
// remove(): 删除第一个元素，内部调用的是removeFirst()


list.removeFirst();
// removeFirst(): 删除第一个元素 


list.removeLast(); 
// removeLast(): 删除最后元素 


list.remove(1); 
// remove(index): 删除index位置的元素


E get(int index) 
//获取下标 index 位置元素


E set(int index, E element) 
//将下标 index 位置元素设置为 element

set(index, elem)
// list.set(0, 100): 将index位置的元素设置为elem

linkedList的遍历

linkedList list = new linkedList<>(); 
list.add(1); // add(elem): 表示尾插 
list.add(2); 
list.add(3); 
list.add(5); 
list.add(6); 
list.add(7); 
System.out.println(list.size()); 
// foreach遍历 
for (int e:list) { 
System.out.print(e + " "); 
}
System.out.println(); 
// 使用迭代器遍历---正向遍历 
ListIterator it = list.listIterator(); 
while(it.hasNext()){ 
System.out.print(it.next()+ " "); 
}
System.out.println(); 
// 使用反向迭代器---反向遍历 
ListIterator rit = list.listIterator(list.size()); 
while (rit.hasPrevious()){ 
System.out.print(rit.previous() +" "); 
}
System.out.println();

三、链表

3.1概念 链表是一种 物理存储结构上非连续 存储结构，数据元素的 逻辑顺序 是通过链表中的 引用链接 次序实现的 。

3.2 无头单向不循环链表

节点：存储数据；节点组织到一起，就变成链表

无头单向非循环链表实现

class Node{//定义一个节点
    public int val;
    public Node next;//类型是Node,next里面存储的是下一个节点的地址

    public Node(int val) {//无法知道下一个节点的地址，只实例化data值
        this.val = val;
    }
}
public class  SinglelinkedList{//链表

    public Node head;//链表的头
    public int usedSize;//记录当前链表节点个数

    public void createList(){
        Node node1=new Node(1);
        Node node2=new Node(2);
        Node node3=new Node(3);
        Node node4=new Node(4);
        Node node5=new Node(5);

        node1.next=node2;//node1存放node2的地址
        node2.next=node3;
        node3.next=node4;
        node4.next=node5;

        this.head=node1;//node1是head  head指向node1引用的对象
        this.usedSize=5;
    }

打印链表里面的元素

//一、打印链表里面的元素
    public void mytToString() {
        Node cur=this.head;
        while (cur!= null) {
            System.out.print(cur.val + " ");
            cur = cur.next;//从当前节点指向下一个
        }
        System.out.println();
    }

查找是否包含关键字key是否在单链表当中

//二、查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        Node cur=this.head;
        while (cur!=null) {
            if (cur.val == key) {//引用类型比较用equals
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

  System.out.println(singlelinkedList.contains(1));

得到单链表的长度

 //三、得到单链表的长度
    public int size1() {
        int count=0;
        Node cur = this.head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return -1;
    }
    public int size2(){
        return this.usedSize;
    }

头插法

 //头插法
    public void addFirst(int data){
        Node node=new Node(data);
        if(head==null){
            head=node;
        }else{
            node.next=head;
            head=node;
        }
        this.usedSize++;
    }

public static void main(String[] args) {
        SinglelinkedList singlelinkedList=new SinglelinkedList();
        singlelinkedList.addFirst(1);
        singlelinkedList.addLast(2);
        singlelinkedList.addLast(3);

尾插法

 //尾插法
    public void addLast(int data){
        Node node=new Node(data);
        Node cur=this.head;
        if (this.head==null){
            head=node;
        }else {
            while (cur.next!=null){
                cur=cur.next;
            }
            cur.next=node;
        }
      this.usedSize++;
    }

 public static void main(String[] args) {
        SinglelinkedList singlelinkedList=new SinglelinkedList();
        singlelinkedList.addLast(1);
        singlelinkedList.addLast(2);
        singlelinkedList.addLast(3);
        singlelinkedList.mytToString();

任意位置插入,第一个数据节点为0号下标

//任意位置插入,第一个数据节点为0号下标
    private Node seachIndex(int index) {//找到indx-1位置
        int count = 0;
        Node cur = this.head;
        while (count != index - 1) {
            cur = cur.next;
            count++;
        }
        return cur;
    }

    public boolean addIndex(int index, int data) {
        if (index < 0 || index > this.usedSize) {//判断index合法
            throw new RuntimeException("index不合法");
        }
        if (index == 0) {
            addFirst(data);
        }
        if (index == this.usedSize) {
            addLast(data);
        }
        Node node = new Node(data);
        Node cur = seachIndex(index);
        node.next = cur.next;
        cur.next = node;
        this.usedSize++;
        return true;
    }

删除第一次出现关键字为key的节点

  //删除第一次出现关键字为key的节点
    public void remove(int key) {
        if (this.head == null) {//判断链表是否为空
            return;
        }
        if (this.head.val == key) {//判断第一个节点关键字是否为key
            this.head = this.head.next;
            return;
        }
        Node prev = findPrevNode(key);
        if (prev == null) {
            throw new RuntimeException("不存在要删除的");
        }
        Node del = prev.next;
        prev.next = del.next;
        this.usedSize--;
    }

        private Node findPrevNode ( int key){
            Node prev = this.head;
            while (prev.next != null) {
                if (prev.next.val == key) {
                    return prev;
                }
                prev=prev.next;//注意
            }
            return null;
        }

删除所有值为key的节点

 //删除所有值为key的节点
    public void removeAllKey(int key){
        if (head==null){//判断是否为空
            return;
        }
        Node prev=this.head;
        Node cur=this.head.next;
        while (cur!=null){
            if (cur.val==key){
                prev.next=cur.next;
                cur=cur.next;
                this.usedSize--;
            }else {
                prev=prev.next;
                cur=cur.next;
            }
            if (this.head.val==key){//判断头节点与key值
                this.head=head.next;
                this.usedSize--;
            }
        }
    }

清空列表

  //清空列表
    public void clear(){
      this.head=null;
      this.usedSize=0;
    }

    public void clear2(){
        Node cur=this.head;
        while (cur!=null) {
            Node curNext=cur.next;
            cur.next=null;
            cur= curNext;
        }
        this.head=null;
        this.usedSize=0;
    }