Java语言----LinkedList 和链表的实现网站首页 技术杂谈

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

逻辑结构：

注：1、如上图，相当于火车车厢，每一节都相连在一起。

2、各个结点连接的方式：通过地址连接，在内存当中，相邻结点在内存中不一定相邻。

3、所有结点都在堆中申请出来。

4、每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

二.链表的分类

1.单向、双向链表

注：无论单向还是双向，都是一个结点存储着下（上）一个结点。

2.带头、不带头结点链表

注：无头和带头结点的主要区别：有一个起始结点。

3.循环、非循环链表

循环链表，就是指：头、尾结点有联系。

在链表结构中，这是主要的链表，但是这些链表种类还可以结合，如：带头双向循环链表、双向循环链表等等。

链表的种类很多，但都大同小异，我们主要学习两种链表：

1、无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。 2、无头双向链表：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表

三.无头单向非循环链表的实现

3.1创建简单链表

重点：每个结点存储着下一个结点的地址。

创建链表代码实现：

public class SingleLinkedList {

      static class List{
        
        int item;   //	存储数据
       
        List next;   //	指向下一个结点
        public List(int item) {
            this.item = item;
        }
        public List() {};
    }

//各种链表实现方法

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

    //得到单链表的长度
public int size(){
    return -1;
}
    //链表的清空
public void clear() {
}
    //展示链表
public void display() {}

3.2 链表基本方法实现

1.遍历链表元素

public void show() {
        //这里不是定义了一个节点 这里只是一个引用
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }

2.获取链表长度

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

3.查询数据

public boolean contains(int key){
        ListNode cur = head;
        while (cur != null) {
            //如果val值 是引用类型  那么这里得用equals来进行比较！！！
            if(cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

4.链表的清空

public void clear() {
        //将所有结点都置空，更为安全
        while (head != null) {
            ListNode headNext = head.next;
            head.next = null;
            head = headNext;
        }
    }

3.3四大基本功能

3.3.1 、增加元素结点

1.头插法：将新增结点放在链表的头部。

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

2.尾插法：将新增结点直接连接在链表的尾部

 public void addLast(int data){
        ListNode node = new ListNode(data);
        if(head == null) {
            head = node;
            return;
        }
        ListNode cur = head;
        while (cur.next != null) {
            cur = cur.next;
        }
        //cur 指向的节点就是尾巴节点
        cur.next = node;
    }

3.选择下标值，添加结点

 public void addIndex(int index,int data){
        int len = size();
        //0、判断index位置的合法性
        if(index < 0 || index > len) {
            throw new IndexOutOfBounds("任意位置插入数据的时候，index位置不合法: "+index);
        }
        if(index == 0) {
            addFirst(data);
            return;
        }
        if(index == len) {
            addLast(data);
            return;
        }
        //1、先找到index-1位置的节点
        ListNode cur = findIndex(index);
        //2、进行插入
        ListNode node = new ListNode(data);
        node.next = cur.next;
        cur.next = node;
}

3.3.2.查找元素结点

查找一个元素，返回对应的下标值。

 public ListNode findIndex(int index) {
        ListNode cur = head;
        while (index - 1 != 0) {
            cur = cur.next;
            index--;
        }
        return cur;//index-1位置的节点
    }

3.3.3.删除元素结点

先找到对应的下标值，然后进行删除。删除方法，前一个结点连接到删除结点的后一个结点。

如图，先断开d2与d3的连接，然后d2直接连接d4

代码实现：

//删除第一次出现关键字为key的节点
    public void remove(int key){
        if(head == null) {
            return;
        }
        //当删除结点为头结点
        if(head.val == key) {
            head = head.next;
            return;
        }
        ListNode prev = searchPrev(key); //返回待删除结点的前一个结点
        if(prev == null) {
            System.out.println("没有这个数据！");
            return;
        }
        ListNode del = prev.next;
        prev.next = del.next;
    }

    private ListNode searchPrev(int key) {
        ListNode prev = head;
        while (prev.next != null) {
            if(prev.next.val == key) {
                return prev;
            }else {
                prev = prev.next;
            }
        }
        return null;
    }

3.3.4.结点信息修改

修改指定下标值的结点元素

public void searchPrev(int num,int date) {
        ListNode prev = head;
       for(int i=0;i<num-1;i++) {
                prev = prev.next;  
        }
        prev.val=date;
    }

四.LinkedList是什么？

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

如图所示：1. LinkedList实现了List接口
2. LinkedList的底层使用了双向链表
3. LinkedList没有实现RandomAccess接口，因此LinkedList不支持随机访问。 4. LinkedList的任意位置插入和删除元素时效率比较高，时间复杂度为O(1)
5. LinkedList比较适合任意位置插入的场景

五.LinkedList使用方法

	方法	解释
构造方法	LinkedList()	无参构造
构造方法	public LinkedList(Collection<? extends E> c)	使用其他集合容器中元素构造List
常用方法	boolean add(E e)	尾插e
	void add(int index,E element)	将e插入到index位置
	boolean addAII(Collection<? extends E> c)	尾插c中的元素
	E remove(int index)	删除index位置元素
	boolean remove(Object o)	删除遇到的第一个o
	E get( int index)	获取下标index位置元素
	void clear()	清空