Java 链表详细介绍(1)

我会带着你远行 2023-09-24 17:38 19阅读 0赞

> 之前我们已经使用**顺序存储结构实现了线性表**，我们会发现虽然**顺序表的查询很快，时间复杂度为O(1),但是增删的效率是比较低的**，因为每一次增删操作都伴随着大量的数据元素移动。这个问题有没有解决方案呢？有，我们可以使用另外一种存储结构实现线性表，链式存储结构。  
> **链表是一种物理存储单元上非连续、非顺序的存储结构**，其物理结构不能只管的表示数据元素的逻辑顺序，数据元素的逻辑顺序是通过`链表中的指针链接次序`实现的。链表由一系列的结点（`链表中的每一个元素称为结点`）组成，结点可以在运行时动态生成。

# 介绍 #

![在这里插入图片描述][15d8035e3ce841428d440e5dded10b60.png]

## 1) 结点API设计： ##

![在这里插入图片描述][b1d37728f47142b3ba72324197f479ea.png]

## 2)结点类实现： ##

public static class Node<T>{
        
            public T item;//存储元素
            public Node next;//指向下一个结点
            public Node(T item,Node next){
        
                this.item = item;
                this.next= next;
            }
        }

## 3)生成链表： ##

public class LinkList {
        
        public static void main(String[] args)throws Exception {
        
            Node<Integer> first = new Node<Integer>(11,null);//构建结点
            Node<Integer> second = new Node<Integer>(11,null);
            Node<Integer> third = new Node<Integer>(11,null);
            Node<Integer> fourth = new Node<Integer>(11,null);
            first.next= second;//生成链表
            second.next = third;
            third.next = fourth;
        }
        public static class Node<T>{
        
            public T item;//存储元素
            public Node next;//指向下一个结点
            public Node(T item,Node next){
        
                this.item = item;
                this.next= next;
            }
        }
    }

# 1.单向链表 #

`单向链表是链表的一种`，它由多个结点组成，**每个结点都由`一个数据域`和`一个指针域`组成**，数据域用来存储数据，`指针域用来指向其后继结点`。`链表的头结点的数据域不存储数据`，**指针域指向第一个真正存储数据的结点**。

![在这里插入图片描述][806d9a52969b4f078c24a7ae12287a5a.png]

## 1)单向链表API设计 ##

![在这里插入图片描述][63f77b2f8ae24137b24d3f92df7b8b65.png]

## 2)单向链表代码实现 ##

import java.util.Iterator;
    
    public class LinkList<T> implements Iterable<T>{
        
        //记录头结点
        private Node head;
        //记录链表的长度
        private int N;
    
    
    
        //结点类
        private class Node {
        
            //存储数据
            T item;
            //下一个结点
            Node next;
    
            public Node(T item, Node next) {
        
                this.item = item;
                this.next = next;
            }
        }
    
        public LinkList() {
        
            //初始化头结点、
            this.head = new Node(null,null);
            //初始化元素个数
            this.N=0;
        }
    
        //清空链表
        public void clear() {
        
            head.next=null;
            this.N=0;
        }
    
        //获取链表的长度
        public int length() {
        
            return N;
        }
    
        //判断链表是否为空
        public boolean isEmpty() {
        
            return N==0;
        }
    
        //获取指定位置i出的元素
        public T get(int i) {
        
    
            //通过循环,从头结点开始往后找，依次找i次，就可以找到对应的元素
            Node n = head.next;
            for(int index=0;index<i;index++){
        
                n=n.next;
            }
    
            return n.item;
        }
    
        //向链表中添加元素t
        public void insert(T t) {
        
            //找到当前最后一个结点
    
            Node n = head;
            while(n.next!=null){
        
                n=n.next;
            }
    
    
            //创建新结点，保存元素t
            Node newNode = new Node(t, null);
            //让当前最后一个结点指向新结点
            n.next=newNode;
            //元素的个数+1
            N++;
        }
    
        //向指定位置i出，添加元素t
        public void insert(int i, T t) {
        
            //找到i位置前一个结点
            Node pre = head;
            for(int index=0;index<=i-1;index++){
        
                pre=pre.next;
            }
    
            //找到i位置的结点
            Node curr = pre.next;
            //创建新结点，并且新结点需要指向原来i位置的结点
            Node newNode = new Node(t, curr);
            //原来i位置的前一个节点指向新结点即可
            pre.next=newNode;
            //元素的个数+1
            N++;
        }
    
        //删除指定位置i处的元素，并返回被删除的元素
        public T remove(int i) {
        
            //找到i位置的前一个节点
            Node pre = head;
            for(int index=0;index<=i-1;i++){
        
                pre=pre.next;
            }
            //要找到i位置的结点
            Node curr = pre.next;
            //找到i位置的下一个结点
            Node nextNode = curr.next;
            //前一个结点指向下一个结点
            pre.next=nextNode;
            //元素个数-1
            N--;
            return curr.item;
        }
    
        //查找元素t在链表中第一次出现的位置
        public int indexOf(T t) {
        
            //从头结点开始，依次找到每一个结点，取出item，和t比较，如果相同，就找到了
            Node n = head;
            for(int i=0;n.next!=null;i++){
        
                n=n.next;
                if (n.item.equals(t)){
        
                    return i;
                }
            }
            return -1;
        }
    
    
        @Override
        public Iterator<T> iterator() {
        
            return new LIterator();
        }
    
        private class LIterator implements Iterator{
        
            private Node n;
            public LIterator(){
        
                this.n=head;
            }
    
            @Override
            public boolean hasNext() {
        
                return n.next!=null;
            }
    
            @Override
            public Object next() {
        
                n = n.next;
                return n.item;
            }
        }
    
        //用来反转整个链表
        public void reverse(){
        
    
            //判断当前链表是否为空链表，如果是空链表，则结束运行，如果不是，则调用重载的reverse方法完成反转
            if (isEmpty()){
        
                return;
            }
    
            reverse(head.next);
        }
    
        //反转指定的结点curr，并把反转后的结点返回
        public Node reverse(Node curr){
        
            if (curr.next==null){
        
                head.next=curr;
                return curr;
            }
            //递归的反转当前结点curr的下一个结点；返回值就是链表反转后，当前结点的上一个结点
            Node pre = reverse(curr.next);
            //让返回的结点的下一个结点变为当前结点curr；
            pre.next=curr;
            //把当前结点的下一个结点变为null
            curr.next=null;
            return curr;
        }
    }

public class Test {
        
        public static void main(String[] args) throws Exception {
        
            LinkList<String> list = new LinkList<>();
            list.insert(0, "张三");
            list.insert(1, "李四");
            list.insert(2, "王五");
            list.insert(3, "赵六");
    //测试length方法
            for (String s : list) {
        
                System.out.println(s);
            }
            System.out.println(list.length());
            System.out.println("-------------------");
    //测试get方法
            System.out.println(list.get(2));
            System.out.println("------------------------");
    //测试remove方法
            String remove = list.remove(1);
            System.out.println(remove);
            System.out.println(list.length());
            System.out.println("----------------");
            ;
            for (String s : list) {
        
                System.out.println(s);
            }
        }
    }

张三
    李四
    王五
    赵六
    4
    -------------------
    王五
    ------------------------

# 2.双向链表 #

`双向链表`也叫双向表，是链表的一种，它**由多个结点组成**，每个结点都由**一个数据域和两个指针域组成**，数据域用来存储数据，其中**一个指针域用来指向其后继结点，另一个指针域用来指向前驱结点**。链表的头结点的数据域不存储数据，**指向前驱结点的指针域值为null，指向后继结点的指针域指向第一个真正存储数据的结点**。

![在这里插入图片描述][383c2d6bebf04eb5b1b3e07c631df333.png]

## 1)双向链表API设计 ##

![在这里插入图片描述][c7fbaf0b9701408388b5f0e47f987616.png]

## 2)双向链表代码实现 ##

public class TowWayLinkList<T> implements Iterable<T> {
        
        //首结点
        private Node head;
        //最后一个结点
        private Node last;
    
        //链表的长度
        private int N;
    
    
    
        //结点类
        private class Node{
        
            public Node(T item, Node pre, Node next) {
        
                this.item = item;
                this.pre = pre;
                this.next = next;
            }
    
            //存储数据
            public T item;
            //指向上一个结点
            public Node pre;
            //指向下一个结点
            public Node next;
        }
    
        public TowWayLinkList() {
        
           //初始化头结点和尾结点
            this.head = new Node(null,null,null);
            this.last=null;
            //初始化元素个数
            this.N=0;
        }
    
        //清空链表
        public void clear(){
        
            this.head.next=null;
            this.head.pre=null;
            this.head.item=null;
            this.last=null;
            this.N=0;
        }
    
        //获取链表长度
        public int length(){
        
            return N;
        }
    
        //判断链表是否为空
        public boolean isEmpty(){
        
            return N==0;
        }
    
        //获取第一个元素
        public T getFirst(){
        
            if (isEmpty()){
        
                return null;
            }
            return head.next.item;
        }
    
        //获取最后一个元素
        public T getLast(){
        
            if (isEmpty()){
        
                return null;
            }
            return last.item;
        }
    
        //插入元素t
        public void insert(T t){
        
    
            if (isEmpty()){
        
                //如果链表为空：
    
                //创建新的结点
                Node newNode = new Node(t,head, null);
                //让新结点称为尾结点
                last=newNode;
                //让头结点指向尾结点
                head.next=last;
            }else {
        
                //如果链表不为空
                Node oldLast = last;
    
                //创建新的结点
                Node newNode = new Node(t, oldLast, null);
    
                //让当前的尾结点指向新结点
                oldLast.next=newNode;
                //让新结点称为尾结点
                last = newNode;
            }
    
            //元素个数+1
            N++;
    
        }
    
        //向指定位置i处插入元素t
        public void insert(int i,T t){
        
            //找到i位置的前一个结点
            Node pre = head;
            for(int index=0;index<i;index++){
        
                pre=pre.next;
            }
            //找到i位置的结点
            Node curr = pre.next;
            //创建新结点
            Node newNode = new Node(t, pre, curr);
            //让i位置的前一个结点的下一个结点变为新结点
            pre.next=newNode;
            //让i位置的前一个结点变为新结点
            curr.pre=newNode;
            //元素个数+1
            N++;
        }
    
        //获取指定位置i处的元素
        public T get(int i){
        
            Node n = head.next;
            for(int index=0;index<i;index++){
        
                n=n.next;
            }
            return n.item;
        }
    
        //找到元素t在链表中第一次出现的位置
        public int indexOf(T t){
        
            Node n = head;
            for(int i=0;n.next!=null;i++){
        
                n=n.next;
                if (n.next.equals(t)){
        
                    return i;
                }
            }
            return -1;
        }
    
        //删除位置i处的元素，并返回该元素
        public T remove(int i){
        
            //找到i位置的前一个结点
            Node pre = head;
            for(int index=0;index<i;index++){
        
                pre=pre.next;
            }
            //找到i位置的结点
            Node curr = pre.next;
            //找到i位置的下一个结点
            Node nextNode= curr.next;
            //让i位置的前一个结点的下一个结点变为i位置的下一个结点
            pre.next=nextNode;
            //让i位置的下一个结点的上一个结点变为i位置的前一个结点
            nextNode.pre=pre;
            //元素的个数-1
            N--;
            return curr.item;
        }
    
        @Override
        public Iterator<T> iterator() {
        
            return new TIterator();
        }
    
        private class TIterator implements Iterator{
        
            private Node n;
            public TIterator(){
        
                this.n=head;
            }
            @Override
            public boolean hasNext() {
        
                return n.next!=null;
            }
    
            @Override
            public Object next() {
        
                n=n.next;
                return n.item;
            }
        }
    }

public class Test {
        
        public static void main(String[] args) throws Exception {
        
            TowWayLinkList<String> list = new TowWayLinkList<>();
            list.insert("张三");
            list.insert("李四");
            list.insert("王五");
            list.insert("赵六");
    
            for (String str : list) {
        
                System.out.println(str);
            }
            System.out.println("----------------------");
            String tow = list.get(2);
            System.out.println(tow);
            System.out.println("-------------------------");
            String remove = list.remove(3);
            System.out.println(remove);
            System.out.println(list.length());
            System.out.println("--------------------");
            System.out.println(list.getFirst());
            System.out.println(list.getLast());    }
    }

张三
    李四
    王五
    赵六
    ----------------------
    王五
    -------------------------

# 3.链表的复杂度分析 #

java中`LinkedList`集合也是`使用双向链表`实现，并提供了增删改查等相关方法  
1.底层是否用双向链表实现；  
2.结点类是否有三个域

`get(int i)`:每一次查询，都需要**从链表的头部开始，依次向后查找，随着数据元素N的增多，比较的元素越多**，时间复杂度为`O(n)`  
`insert(int i,T t)`:每一次插入，**需要先找到i位置的前一个元素，然后完成插入操作**，随着数据元素N的增多，查找的元素越多，时间复杂度为`O(n)`;  
`remove(int i)`:每一次移除，**需要先找到i位置的前一个元素**，然后完成插入操作，随着数据元素N的增多，查找的元  
素越多，时间复杂度为`O(n)`

*  **相比较顺序表**，链表插入和删除的时间复杂度虽然一样，但仍然有很大的优势，因为链表的物理地址是不连续的，它不需要预先指定存储空间大小，或者在存储过程中涉及到扩容等操作,同时它并没有涉及的元素的交换。
 *  **相比较顺序表**，链表的查询操作性能会比较低。因此，如果我们的程序中查询操作比较多，建议使用顺序表，增删操作比较多，建议使用链表。

[15d8035e3ce841428d440e5dded10b60.png]: https://img-blog.csdnimg.cn/15d8035e3ce841428d440e5dded10b60.png
[b1d37728f47142b3ba72324197f479ea.png]: https://img-blog.csdnimg.cn/b1d37728f47142b3ba72324197f479ea.png
[806d9a52969b4f078c24a7ae12287a5a.png]: https://img-blog.csdnimg.cn/806d9a52969b4f078c24a7ae12287a5a.png
[63f77b2f8ae24137b24d3f92df7b8b65.png]: https://img-blog.csdnimg.cn/63f77b2f8ae24137b24d3f92df7b8b65.png
[383c2d6bebf04eb5b1b3e07c631df333.png]: https://img-blog.csdnimg.cn/383c2d6bebf04eb5b1b3e07c631df333.png
[c7fbaf0b9701408388b5f0e47f987616.png]: https://img-blog.csdnimg.cn/c7fbaf0b9701408388b5f0e47f987616.png