链表（LinkedList）-EW帮帮网

链表

链表：⼀种物理存储结构上⾮连续存储结构，数据元素的逻辑顺序是通过链表中的引⽤链接次序实现的

链表结构

LinkedList单向链表

LinkedList的创建与打印

public class MyLinkedList {
    static class ListNode{
       public int val;
       public ListNode next;
       public ListNode(int val){
           this.val=val;
       }
    }
    public ListNode head;
    public void creatList(){
        ListNode node1=new ListNode(11);
        ListNode node2=new ListNode(22);
        ListNode node3=new ListNode(33);
        ListNode node4=new ListNode(44);
        ListNode node5=new ListNode(55);
        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
        node4.next=node5;
        this.head=node1;
    }
    public void print(){
        ListNode cur=head;
        while(cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
        System.out.println();
    }
}

public class Test {
    public static void main(String[] args) {
        MyLinkedList myLinkedList=new MyLinkedList();
        myLinkedList.creatList();
        myLinkedList.print();
    }
}

LinkedList的头插法

public void addFirst(int data) {
    ListNode node=new ListNode(data);
    node.next=head;
    head=node;
}

public class Test {
    public static void main(String[] args) {
        MyLinkedList myLinkedList=new MyLinkedList();
        myLinkedList.addFirst(1);
        myLinkedList.addFirst(2);
        myLinkedList.addFirst(3);
        myLinkedList.print();
    }
}

LinkedList的尾插法

public void addLast(int data) {
    ListNode node=new ListNode(data);
    ListNode cur=head;
    if(cur==null){
        head=node;
        return;
    }
    while (cur.next!=null){
        cur=cur.next;
    }
    cur.next=node;
}
public class Test {
    public static void main(String[] args) {
        MyLinkedList myLinkedList=new MyLinkedList();
        myLinkedList.addLast(10);
        myLinkedList.addLast(20);
        myLinkedList.addLast(30);
        myLinkedList.print();
    }
}

LinkedList的指定位置插入法

public void addIndex(int index, int data) {
    if(index<0||index>size()){
        return ;
    }
    if (index==0){
        addFirst(data);
        return;
    }
    if(index==size()){
        addLast(data);
        return;
    }
    ListNode node=new ListNode(data);
    ListNode cur=searchIndex(index);
    if(cur==null){
        return;
    }
    node.next=cur.next;
    cur.next=node;

}
public ListNode searchIndex(int index){
if(index<0||index>size()){
      return null;
}
ListNode cur=head;
int count=0;
while (count!=index-1){
      cur=cur.next;
      count++;
}
return cur;
}

public class Test {
    public static void main(String[] args) {
        MyLinkedList myLinkedList=new MyLinkedList();
        myLinkedList.creatList();
        myLinkedList.print();
        myLinkedList.addIndex(0,0);
        myLinkedList.addIndex(6,66);
        myLinkedList.print();
    }
}

Linked List的contains方法

public boolean contains(int key) {
    ListNode cur=head;
    while(cur!=null){
        if(cur.val==key){
            return true;
        }
        cur=cur.next;
    }
    return false;
}

public class Test {
    public static void main(String[] args) {
        MyLinkedList myLinkedList=new MyLinkedList();
        myLinkedList.creatList();
        System.out.println(myLinkedList.contains(33));
        System.out.println(myLinkedList.contains(66));

    }
}

LinkedList的删除第一次出现的key关键字

public ListNode searchIndex(int index){
  if(index<0||index>size()){
      return null;
  }
  ListNode cur=head;
  int count=0;
  while (count!=index-1){
      cur=cur.next;
      count++;
  }
  return cur;
}

// 查找是否包含关键字 key 是否在单链表当中
public boolean contains(int key) {
    ListNode cur=head;
    while(cur!=null){
        if(cur.val==key){
            return true;
        }
        cur=cur.next;
    }
    return false;
}

public class Test {
    public static void main(String[] args) {
        MyLinkedList myLinkedList=new MyLinkedList();
        myLinkedList.addLast(10);
        myLinkedList.addLast(20);
        myLinkedList.addLast(30);
        myLinkedList.addLast(40);
        myLinkedList.print();
        myLinkedList.remove(30);
        myLinkedList.print();
    }
}

LinkedList的删除所有key关键字

public void removeAllKey(int key) {
    if (head==null){
        return;
    }
    ListNode prev=head;
    ListNode cur=head.next;
    while (cur!=null){
        if (cur.val==key){
            prev.next=cur.next;
            cur=cur.next;
        }else {
            prev=cur;
            cur=cur.next;
        }
    }
    if (head.val==key){
        head=head.next;
    }
}

public class Test {
    public static void main(String[] args) {
        MyLinkedList myLinkedList=new MyLinkedList();
        myLinkedList.addLast(10);
        myLinkedList.addLast(30);
        myLinkedList.addLast(20);
        myLinkedList.addLast(30);
        myLinkedList.addLast(40);
        myLinkedList.addLast(30);
        myLinkedList.print();
        myLinkedList.removeAllKey(30);
        myLinkedList.print();

    }
}

LinkedList的size()方法

public int size() {
    ListNode cur=head;
    int count=0;
    while (cur!=null){
        count++;
        cur=cur.next;
    }
    return count;
}

public class Test {
    public static void main(String[] args) {
        MyLinkedList myLinkedList=new MyLinkedList();
        myLinkedList.creatList();
        System.out.println(myLinkedList.size());
    }
}

LinkedList的clear方法

public void clear() {
    head=null;
}

public class Test {
    public static void main(String[] args) {
        MyLinkedList myLinkedList=new MyLinkedList();
        myLinkedList.creatList();
        myLinkedList.print();
        myLinkedList.clear();
        System.out.println("clear之后：");
        myLinkedList.print();
    }
}

LinkedList的完整实现

public class MyLinkedList {
    static class ListNode{
       public int val;
       public ListNode next;
       public ListNode(int val){
           this.val=val;
       }
    }
    public ListNode head;
    public ListNode last;
    public void creatList(){
        ListNode node1=new ListNode(11);
        ListNode node2=new ListNode(22);
        ListNode node3=new ListNode(33);
        ListNode node4=new ListNode(44);
        ListNode node5=new ListNode(55);
        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
        node4.next=node5;
        this.head=node1;
    }
    public void print(){
        ListNode cur=head;
        while(cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
        System.out.println();
    }
    // 头插法
    public void addFirst(int data) {
        ListNode node=new ListNode(data);
        node.next=head;
        head=node;
    }

    // 尾插法
    public void addLast(int data) {
        ListNode node=new ListNode(data);
        ListNode cur=head;
        if(cur==null){
            head=node;
            return;
        }
        while (cur.next!=null){
            cur=cur.next;
        }
        cur.next=node;
    }

    // 任意位置插入，第一个数据节点为 0 号下标
    public void addIndex(int index, int data) {
        if(index<0||index>size()){
            return ;
        }
        if (index==0){
            addFirst(data);
            return;
        }
        if(index==size()){
            addLast(data);
            return;
        }
        ListNode node=new ListNode(data);
        ListNode cur=searchIndex(index);
        if(cur==null){
            return;
        }
        node.next=cur.next;
        cur.next=node;

    }
    public ListNode searchIndex(int index){
      if(index<0||index>size()){
          return null;
      }
      ListNode cur=head;
      int count=0;
      while (count!=index-1){
          cur=cur.next;
          count++;
      }
      return cur;
    }

    // 查找是否包含关键字 key 是否在单链表当中
    public boolean contains(int key) {
        ListNode cur=head;
        while(cur!=null){
            if(cur.val==key){
                return true;
            }
            cur=cur.next;
        }
        return false;
    }

    // 删除第一次出现关键字为 key 的节点
    public void remove(int key) {
        if (head==null){
            return;
        }
        if (head.val==key){
            head=head.next;
            return;
        }
        ListNode pre=findKey(key);
        if (pre==null){
            return;
        }
        ListNode delete=pre.next;
        pre.next=delete.next;
    }
    public ListNode findKey(int key){
        ListNode prev=head;
        while (prev.next!=null){
            if(prev.next.val==key){
                return prev;
            }
            prev = prev.next;
        }
        return null;
    }
    // 删除所有值为 key 的节点
    public void removeAllKey(int key) {
        if (head==null){
            return;
        }
        ListNode prev=head;
        ListNode cur=head.next;
        while (cur!=null){
            if (cur.val==key){
                prev.next=cur.next;
                cur=cur.next;
            }else {
                prev=cur;
                cur=cur.next;
            }
        }
        if (head.val==key){
            head=head.next;
        }
    }

    // 得到单链表的长度
    public int size() {
        ListNode cur=head;
        int count=0;
        while (cur!=null){
            count++;
            cur=cur.next;
        }
        return count;
    }

    public void clear() {
        head=null;
    }
    
}

DoubleLinked List双向链表

Double Linked List的头插法

public void addFirst(int data) {
    LinkedNode node=new LinkedNode(data);
    if(head==null){
        head=node;
        last=node;
    }else {
        node.next=head;
        head.prev=node;
        head=node;
    }
}

DoubleLinkedList的尾插法

public void addLast(int data) {
    LinkedNode node=new LinkedNode(data);
    if (head==null){
        head=node;
        last=node;
    }else {
        last.next=node;
        node.prev=last;
        last=node;
    }
}

DoubleLinkedList的任意位置插入的方法

public void addIndex(int index, int data) {
    if (index<0||index>size()){
        System.out.println("下标位置不合法："+index);
        return;
    }
    if (index==0){
        addFirst(data);
        return;
    }
    if(index==size()){
        addLast(data);
        return;
    }
    LinkedNode node=new LinkedNode(data);
    LinkedNode cur=search(index);
    node.next=cur;
    cur.prev.next=node;
    node.prev=cur.prev;
    cur.prev=node;
}
public LinkedNode search(int index){
    LinkedNode cur=head;
    while (index!=0){
        cur=cur.next;
        index--;
    }
    return cur;
}

DoubleLinkedList删除key节点的方法

// 删除第一次出现关键字为 key 的节点
public void remove(int key) {
    LinkedNode cur=head;
    while (cur!=null){
        if(cur.val == key) {
            if(cur == head) {
                //删除头节点
                head = head.next;
                if(head == null) {
                    //只有一个节点的情况下
                    last = null;
                }else {
                    head.prev = null;
                }
            }else {
                //删除中间和尾巴
                if(cur.next == null) {
                    //尾巴
                    cur.prev.next = cur.next;
                    last = last.prev;
                }else {
                    cur.prev.next = cur.next;
                    cur.next.prev = cur.prev;
                }
            }
            return;
        }
        cur = cur.next;
    }
}

// 删除所有值为 key 的节点
public void removeAllKey(int key) {
    LinkedNode cur = head;
    while (cur != null) {
        if(cur.val == key) {
            if(cur == head) {
                //删除头节点
                head = head.next;
                if(head == null) {
                    //只有一个节点的情况下
                    last = null;
                }else {
                    head.prev = null;
                }
            }else {
                //删除中间和尾巴
                if(cur.next == null) {
                    //尾巴
                    cur.prev.next = cur.next;
                    last = last.prev;
                }else {
                    cur.prev.next = cur.next;
                    cur.next.prev = cur.prev;
                }
            }
        }
        cur = cur.next;
    }
}

DoubleLinkedList的contains（）方法

public boolean contains(int key) {
    LinkedNode cur=head;
    while (cur!=null){
       if (cur.val==key){
           return true;
       }
        cur=cur.next;
    }
    return false;
}

Double Linked List的size（）方法

public int size() {
    LinkedNode cur=head;
    int count=0;
    while (cur!=null){
        count++;
        cur=cur.next;
    }
    return count;
}

Double Linked List的display()方法

public void display() {
    LinkedNode cur=head;
    while (cur!=null){
        System.out.print(cur.val+" ");
        cur=cur.next;
    }
    System.out.println();
}

DoubleLinkedList的clear()方法

public void clear() {
    LinkedNode cur = head;
    while (cur != null) {
        LinkedNode curN = cur.next;

        cur.prev = null;
        cur.next = null;
        cur = curN;
    }
    head = null;
    last = null;
}

DoubleLinkedList的完整实现

public class DoubleLinkedList {
    static class LinkedNode{
        public int val;
        public LinkedNode next;
        public LinkedNode prev;
        public LinkedNode(int val){
            this.val=val;
        }
    }
    public LinkedNode head;
    public LinkedNode last;

    public void addFirst(int data) {
        LinkedNode node=new LinkedNode(data);
        if(head==null){
            head=node;
            last=node;
        }else {
            node.next=head;
            head.prev=node;
            head=node;
        }
    }

    // 尾插法
    public void addLast(int data) {
        LinkedNode node=new LinkedNode(data);
        if (head==null){
            head=node;
            last=node;
        }else {
            last.next=node;
            node.prev=last;
            last=node;
        }
    }

    // 任意位置插入，第一个数据节点为 0 号下标
    public void addIndex(int index, int data) {
        if (index<0||index>size()){
            System.out.println("下标位置不合法："+index);
            return;
        }
        if (index==0){
            addFirst(data);
            return;
        }
        if(index==size()){
            addLast(data);
            return;
        }
        LinkedNode node=new LinkedNode(data);
        LinkedNode cur=search(index);
        node.next=cur;
        cur.prev.next=node;
        node.prev=cur.prev;
        cur.prev=node;
    }
    public LinkedNode search(int index){
        LinkedNode cur=head;
        while (index!=0){
            cur=cur.next;
            index--;
        }
        return cur;
    }

    // 查找是否包含关键字 key 是否在单链表当中
    public boolean contains(int key) {
        LinkedNode cur=head;
        while (cur!=null){
           if (cur.val==key){
               return true;
           }
            cur=cur.next;
        }
        return false;
    }

    // 删除第一次出现关键字为 key 的节点
    public void remove(int key) {
        LinkedNode cur=head;
        while (cur!=null){
            if(cur.val == key) {
                if(cur == head) {
                    //删除头节点
                    head = head.next;
                    if(head == null) {
                        //只有一个节点的情况下
                        last = null;
                    }else {
                        head.prev = null;
                    }
                }else {
                    //删除中间和尾巴
                    if(cur.next == null) {
                        //尾巴
                        cur.prev.next = cur.next;
                        last = last.prev;
                    }else {
                        cur.prev.next = cur.next;
                        cur.next.prev = cur.prev;
                    }
                }
                return;
            }
            cur = cur.next;
        }
    }

    // 删除所有值为 key 的节点
    public void removeAllKey(int key) {
        LinkedNode cur = head;
        while (cur != null) {
            if(cur.val == key) {
                if(cur == head) {
                    //删除头节点
                    head = head.next;
                    if(head == null) {
                        //只有一个节点的情况下
                        last = null;
                    }else {
                        head.prev = null;
                    }
                }else {
                    //删除中间和尾巴
                    if(cur.next == null) {
                        //尾巴
                        cur.prev.next = cur.next;
                        last = last.prev;
                    }else {
                        cur.prev.next = cur.next;
                        cur.next.prev = cur.prev;
                    }
                }
            }
            cur = cur.next;
        }
    }
    // 得到单链表的长度
    public int size() {
        LinkedNode cur=head;
        int count=0;
        while (cur!=null){
            count++;
            cur=cur.next;
        }
        return count;
    }

    // 遍历显示链表元素（假设功能），实际可根据需求定义
    public void display() {
        LinkedNode cur=head;
        while (cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
        System.out.println();
    }

    // 清空链表
    public void clear() {
        LinkedNode cur = head;
        while (cur != null) {
            LinkedNode curN = cur.next;
            //cur.val = null;
            cur.prev = null;
            cur.next = null;
            cur = curN;
        }
        head = null;
        last = null;
    }
}

Linked List的使用

【说明】

1. LinkedList实现了List接⼝

2. LinkedList的底层使⽤了双向链表

3. LinkedList没有实现RandomAccess接⼝，因此LinkedList不⽀持随机访问

4. LinkedList的任意位置插⼊和删除元素时效率⽐较⾼，时间复杂度为O(1)

5. LinkedList⽐较适合任意位置插⼊的场景

LinkedList的常用方法

import java.util.LinkedList;

public class Test {
    public static void main(String[] args) {
        LinkedList<Integer> linkedList=new LinkedList<>();
        LinkedList<Integer> linkedList1=new LinkedList<>();
        linkedList1.add(55);
        linkedList1.add(66);
        //尾插
        linkedList.add(11);
        linkedList.add(22);
        linkedList.add(33);
        System.out.println(linkedList);
        //元素插入index位置
        linkedList.add(0,0);
        linkedList.add(4,44);
        System.out.println(linkedList);
        //插入其他链表的元素
        linkedList.addAll(linkedList1);
        System.out.println(linkedList);
        //删除元素
        linkedList.remove(0);
        linkedList.remove(4);
        System.out.println(linkedList);
        //获取下标元素
        System.out.println(linkedList.get(3));
        //设置index元素
        linkedList.set(1,111);
        System.out.println(linkedList);
        //判断元素是否存在
        System.out.println(linkedList.contains(44));
        System.out.println(linkedList.contains(22));
        //返回下标
        System.out.println(linkedList.indexOf(55));
        System.out.println(linkedList.lastIndexOf(111));
        //截取
        System.out.println(linkedList.subList(0, 4));
        //清空
        System.out.println(linkedList);
        linkedList.clear();
        System.out.println(linkedList);
    }
}

Linked List的遍历

import java.util.LinkedList;
import java.util.ListIterator;
public class Test {
    public static void main(String[] args) {
        LinkedList<Integer> linkedList=new LinkedList<>();
        linkedList.add(1);
        linkedList.add(2);
        linkedList.add(3);
        //直接遍历
        System.out.println(linkedList);
        //for循环遍历
        for (int i = 0; i <linkedList.size() ; i++) {
            System.out.print(linkedList.get(i)+" ");
        }
        System.out.println();
        //foreach遍历
        for (int i:linkedList) {
            System.out.print(i+" ");
        }
        System.out.println();
        //迭代器遍历
        ListIterator<Integer> iterator=linkedList.listIterator();
        while (iterator.hasNext()){
            System.out.print(iterator.next()+" ");
        }
        System.out.println();
        ListIterator<Integer> iterator1=linkedList.listIterator(linkedList.size());
        while (iterator1.hasPrevious()){
            System.out.print(iterator1.previous()+" ");
        }
        System.out.println();

    }

链表（LinkedList）

链表

链表结构

LinkedList单向链表

LinkedList的创建与打印

LinkedList的头插法

LinkedList的尾插法

LinkedList的指定位置插入法

Linked List的contains方法

LinkedList的删除第一次出现的key关键字

LinkedList的删除所有key关键字

LinkedList的size()方法

LinkedList的clear方法

LinkedList的完整实现

DoubleLinked List双向链表

Double Linked List的头插法

DoubleLinkedList的尾插法

DoubleLinkedList的任意位置插入的方法

DoubleLinkedList删除key节点的方法

DoubleLinkedList的contains（）方法

public boolean contains(int key) {
    LinkedNode cur=head;
    while (cur!=null){
       if (cur.val==key){
           return true;
       }
        cur=cur.next;
    }
    return false;
}

Double Linked List的size（）方法

Double Linked List的display()方法

DoubleLinkedList的clear()方法

DoubleLinkedList的完整实现

Linked List的使用

LinkedList的常用方法

Linked List的遍历

网站公告

今日签到

热门文章

最新发布

链表（LinkedList）

链表

链表结构

LinkedList单向链表

LinkedList的创建与打印

LinkedList的头插法

LinkedList的尾插法

LinkedList的指定位置插入法

Linked List的contains方法

LinkedList的删除第一次出现的key关键字

LinkedList的删除所有key关键字

LinkedList的size()方法

LinkedList的clear方法

LinkedList的完整实现

DoubleLinked List双向链表

Double Linked List的头插法

DoubleLinkedList的尾插法

DoubleLinkedList的任意位置插入的方法

DoubleLinkedList删除key节点的方法

DoubleLinkedList的contains（）方法 public boolean contains(int key) { LinkedNode cur=head; while (cur!=null){ if (cur.val==key){ return true; } cur=cur.next; } return false; }

Double Linked List的size（）方法

Double Linked List的display()方法

DoubleLinkedList的clear()方法

DoubleLinkedList的完整实现

Linked List的使用

LinkedList的常用方法

Linked List的遍历

网站公告

今日签到

热门文章

最新发布

DoubleLinkedList的contains（）方法

public boolean contains(int key) {
LinkedNode cur=head;
while (cur!=null){
if (cur.val==key){
return true;
}
cur=cur.next;
}
return false;
}