数据结构---------链表

古城微笑少年丶 2022-04-22 14:00 248阅读 0赞

一、链表为什么存在？  
      1）.数组的缺陷  
                   无序列表：搜索性能差，有序列表：插入效率低，并且两个的删除效率也很低，数组在创建后大小就固定了，设置的过大会造成内存浪费，过小又不能满足数据量的存储  
      2）.解决上诉一部分问题

二、链表简介

1）.链表通常由一连串节点组成，每个节点包含任意的实例数据（data fields）和一或两个用来指向上一个/或下一个节点的位置的链接（"links"）

三、有什么优点？  
      1.克服数组需要预先知道数据大小的缺点

2.充分利用计算机内存空间，实现灵活的内存动态管理

四、缺点

1.失去了数组随机读取的优点

2.由于增加了节点的指针域，空间开销比较大

五、单向链表

1.结构：一部分保存或者显示关于节点的信息，另一部分存储下一个节点的地址

注：最后一个节点存储地址的部分指向空值。

2.简介

①遍历：单向链表只可向一个方向遍历，一般查找一个节点的时候需要从第一个节点开始每次访问下一个节点，一直访问到需要的位置

图解：

![20181105182727110.png][]

②增加：单向链表只可向一个方向遍历，一般查找一个节点的时候需要从第一个节点开始每次访问下一个节点，一直访问到需要的位置

图解：

![20181105182741555.png][]

③删除

图解：

![20181105182752921.png][]

④代码实现单链表思路

1）定义一个类，包含Object data数据信息字段和 节点类类名 next信息字段

2）编写功能链表头添加元素

3）在链表头删除元素

4）查找指定元素，返回找到的节点Node找不到则返回null

5）删除指定的元素，删除成功返回true

6）判断链表是否为空

7）显示节点

⑤代码

1.节点类（Node）

/**
     * @program: Linked_List01
     * @description:
     * @author: Mr.Liu
     * @create: 2018-11-04 21:10
     **/
    public class Node {
    
    
        private Node next;
        private Object data;
        public Node(Object data){
            this.data=data;
        }
    
        public Node getNext() {
            return next;
        }
    
        public void setNext(Node next) {
            this.next = next;
        }
    
        public Object getData() {
            return data;
        }
    
        public void setData(Object data) {
            this.data = data;
        }
    
    
    }

2.单链表类（SingleLinkedList）

public class SingleLinkedList {
        //1.单链表内置字段，head：头结点  size：节点个数
        private Node head;
        private int size;
    
        //2.调用创建时默认值
        public SingleLinkedList(){
            this.size=0;
            this.head=null;
        }
    
        //3.链表添加头节点
        public Object addHead(Object obj){
            Node newHead=new Node(obj);
            if (size==0){
                head=newHead;
            }else{
                newHead.setNext(head);
                head=newHead;
            }
            size++;
            return obj;
        }
    
        //4.删除链表头结点
        public Object deleteHead(){
            Object obj=head.getData();
            head.setNext(null);
            size--;
            return obj;
        }
    
        //5.查找指定元素，找到了返回节点，没有返回null;??
        public Node find(Object obj){
            Node current =head;
            int tempSize =size;
            while(tempSize>=0){
                if (obj.equals(current.getData())){
                    return current;
                }else{
                    current = current.getNext();
                }
                tempSize--;
            }
            return null;
        }
    
        //6.删除指定的元素，删除成功返回true
        //1).上一个节点指向下一个节点，匹配的节点信息至空
        public boolean delete(Object value){
            if (size==0){
                return false;
            }
            Node previos=head;
            Node current=head;
            //获取节点信息
            while(value!=current.getData()){
                if (current.getNext()==null){
                    return false;
                }else{
                    previos=current;
                    current=current.getNext();
                }
            }
            //删除节点   1.如果是头节点    2.不是头节点
            if (current==head){
                head = current.getNext();
                size--;
            }else{
                previos.setNext(current.getNext());
                size--;
            }
            return true;
        }
    
        //7.判断链表是否为空
        public boolean isEmpty(){
            return (size==0);
        }
    
        //8.显示节点信息
        public void display(){
            if(size>0){
                Node node = head;
                int tempSize = size;
                if(tempSize == 1) {//当前链表只有一个节点
                    System.out.println("[" + node.getData() + "]");
                    return;
                }
                while(tempSize>0){
                    if(node.equals(head)){
                        System.out.print("["+node.getData()+"->");
                    }else if(node.getNext() == null){
                        System.out.print(node.getData()+"]");
                    }else{
                        System.out.print(node.getData()+"->");
                    }
                    node = node.getNext();
                    tempSize--;
                }
                System.out.println();
            }else {//如果链表一个节点都没有，直接打印[]
                System.out.println("[]");
            }
        }
    }

3. 测试

public class Main {
        public static void main(String[] args) {
            SingleLinkedList singleList = new SingleLinkedList();
            System.out.println(singleList.addHead("aa"));
            System.out.println(singleList.addHead("bb"));
            System.out.println(singleList.addHead("cc"));
            //打印当前链表信息
            singleList.display();
            //删除aa
            singleList.delete("aa");
            singleList.display();
            //查找bb
            System.out.println(singleList.find("bb"));
        }
    }

4.结果：

![20181105182815489.png][]

⑥双端链表

单项链表，我们如果想在尾部添加一个节点，那么必须从头部一直遍历到尾部，找到尾节点，然后在尾节点后面插入一个节点。这样操作很麻烦，如果我们在设计链表的时候多个对尾节点的引用，那么会简单很多

图解：

![201811051828176.png][]

⑦双向链表：

单向链表只能从一个方向遍历，那么双向链表它可以从两个方向遍历

图解：

![20181105182823562.png][]

# #

## 补充链表结构——头结点与头指针 ##

图解：  
![20190117000332638.png][]

头指针:

1.  在线性表的链式存储结构中，头指针是指链表指向第一个结点的指针，若链表有头结点，则头指针就是指向链表头结点的指针。
2.  头指针具有标识作用，故常用头指针冠以链表的名字。
3.  无论链表是否为空，头指针均不为空。头指针是链表的必要元素。

头结点:

1.  头结点是为了操作的统一与方便而设立的，放在第一个元素结点之前，其数据域一般无意义（当然有些情况下也可存放链表的长度、用做监视哨等等）。
2.  结点的存在使得空链表与非空链表处理一致，也方便对链表的开始结点的插入或删除操作。
3.  首元结点也就是第一个元素的结点，它是头结点后边的第一个结点。
4.  头结点不是链表所必需的。

[https://me.csdn.net/qq\_39657909][https_me.csdn.net_qq_39657909]

[20181105182727110.png]: /images/20220422/7cf58a8999244409abdc79be9752297a.png
[20181105182741555.png]: /images/20220422/762710bfaf614cc89fd8834286a5a3e9.png
[20181105182752921.png]: /images/20220422/6e9ca7ff71b442f48dd64973b65aec03.png
[20181105182815489.png]: /images/20220422/3ecf7328be1f4608912ca5f1d7243f6b.png
[201811051828176.png]: /images/20220422/3f6c23c87145441d823d5f7bd35e70f9.png
[20181105182823562.png]: /images/20220422/860c0572eb1946eea58708038b9c6c3e.png
[20190117000332638.png]: /images/20220422/203dc755e33f456c8c12ad585c9090cf.png
[https_me.csdn.net_qq_39657909]: https://me.csdn.net/qq_39657909