链表-Java实现链表数据结构

骑猪看日落 2023-02-16 06:03 43阅读 0赞

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

**链表(Linked list)**：是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数 据，而是在每一个节点里存到下一个节点的指针(Pointer)。  
使用链表结构可以克服数组需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针  
域，空间开销比较大。

#### 单向链表 ####

单链表是链表中结构最简单的。一个单链表的节点(Node)分为两个部分，第一个部分(data)保存或者显示关于节点的信息，另一个部分存储下一个节点的地址。最后一个节点存储地址的部分指向空值。  
单向链表只可向一个方向遍历，一般查找一个节点的时候需要从第一个节点开始每次访问下一个节 点，一直访问到需要的位置。而插入一个节点，对于单向链表，我们只提供在链表头插入，只需要将当 前插入的节点设置为头节点，next指向原头节点即可。删除一个节点，我们将该节点的上一个节点的 next指向该节点的下一个节点  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTEzNDMw_size_16_color_FFFFFF_t_70]  
在表头增加节点：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTEzNDMw_size_16_color_FFFFFF_t_70 1]  
在表头删除节点：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTEzNDMw_size_16_color_FFFFFF_t_70 2]

/**
     * @author shihaowei
     * @date 2020-06-03 16:28
     */
    public class SingleLinkList {
        
    
        private int size;
        private Node head;
    
    
        public SingleLinkList() {
        
    
            this.size = 0;
            this.head = null;
        }
    
        /** 内部类节点 */
        public class Node {
        
    
            private Object data;
            private Node next;
    
            public Node(Object data) {
        
                this.data = data;
            }
    
            @Override
            public String toString() {
        
                return "Node{" +
                        "data=" + data +
                        ", next=" + next +
                        '}';
            }
        }
    
        /** 添加节点 */
        public Object addHead(Object obj){
        
    
            Node newNode = new Node(obj);
            if (size == 0){
        
                head = newNode;
    
            }else {
        
                newNode.next = head;
                head = newNode;
            }
            size++;
            return obj;
        }
    
        /** 删除头节点 */
        public Object delHead(){
        
            if (size > 0){
        
                Object data = head.data;
                head = head.next;
                size--;
                return data;
            }
            return false;
        }
    
    
        /** 获取指定数据节点*/
        public Node find(Object value){
        
    
            Node current = head;
            int tempsize = size;
             while (tempsize>0){
        
    
                 if (current.data.equals(value)){
        
                     return current;
                 }else {
        
                     current = current.next;
                     tempsize--;
                 }
             }
             return null;
        }
    
        /** 删除数据节点*/
        public boolean delValue(Object value){
        
            if (size == 0){
        
                return false;
            }
            Node current = head;
            Node prenode = head;
    
            while (!current.data.equals(value)){
        
    
                if (current.next == null){
        
                    return false;
                }else {
        
                    prenode = current;
                    current = current.next;
                }
            }
    
            //如果第一个节点就是要删除的
            if (current == head){
        
                head = current.next;
                size--;
            }else {
        
                prenode.next = current.next;
                size--;
            }
    
            return true;
        }
    
    
        @Override
        public String toString() {
        
            return "SingleLinkList{" +
                    "size=" + size +
                    ", head=" + head +
                    '}';
        }
    
        public static void main(String[] args) {
        
    
            SingleLinkList linkList = new SingleLinkList();
            linkList.addHead("a");
            linkList.addHead("b");
            linkList.addHead("c");
    
            //linkList.delHead();
            System.out.println(linkList);
        }
    
    
    }

#### 双端链表 ####

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

public class DoublePointLinklist {
        
    
        private Node head;
        private Node tail;
        private int size;
    
        // 链表的节点类
        private class Node{
        
    
            private Object data;
            private Node next;
    
            public Node(Object data) {
        
                this.data = data;
            }
        }
    
        public DoublePointLinklist() {
        
            this.head = null;
            this.tail = null;
            this.size = 0;
        }
    
        /**
         * 头节点插入
         * @param data
         * @return
         */
        public Object addHead(Object data){
        
    
            Node node = new Node(data);
            if (head.next == null){
        
                head = node;
                tail = node;
            }else {
        
                head.next = head;
                head = node;
            }
            size++;
            return data;
    
        }
    
        /**
         * 尾节点插入
         * @param data
         * @return
         */
        public Object addTail(Object data){
        
    
            Node node = new Node(data);
            if (head.next == null) {
        
                head = node;
                tail = node;
            }else {
        
                tail.next = tail;
                tail = node;
            }
            size++;
            return data;
        }
    
    
        /**
         * 删除节点
         * @param data
         * @return
         */
        public boolean delNode(Object data){
        
            if ( size == 0){
        
                return false;
            }
    
            Node prenode = head;
            Node current = head;
            while (!head.data.equals(data)){
        
                if (current.next == null){
        
                    return false;
                }else {
        
                    prenode = current;
                    current = current.next;
                }
            }
    
            if (current == head){
        
                head = current.next;
            }else {
        
                prenode.next = current.next;
            }
    
            size--;
            return true;
        }
    }

#### 双向链表 ####

我们知道单向链表只能从一个方向遍历，那么双向链表它可以从两个方向遍历  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTEzNDMw_size_16_color_FFFFFF_t_70 4]

package person.shw.datastructure.link;
    
    /**
     * @author shihaowei
     * @date 2020-06-08 16:39
     */
    public class TwoWayLinkedList {
        
    
        private Node head;
        private Node tail;
        private int size;
    
    
        /**
         * 节点类
         */
        private class Node{
        
    
            private Object object;
            private Node next;
            private Node pre;
    
            public Node(Object object) {
        
                this.object = object;
            }
        }
    
        public TwoWayLinkedList() {
        
            size = 0;
            head = null;
            tail = null;
        }
    
    
        /**
         * 链表头增加节点
         * @param obj
         */
        public void addHead(Object obj){
        
    
            Node node = new Node(obj);
    
            if (size == 0){
        
                head = node;
                tail = node;
            }else {
        
                head.pre = node;
                head.next = head;
                head = node;
            }
            size++;
        }
    
        /**
         * 链表尾添加节点
         * @param obj
         */
        public void addTail(Object obj){
        
    
            Node node = new Node(obj);
    
            if (size == 0) {
        
                head = node;
                tail = node;
            }else {
        
                tail.next = node;
                node.pre = tail;
                tail = node;
            }
            size++;
        }
    
    
        /**
         * 删除头节点
         * @return
         */
        public Object deleteHead(){
        
    
            Node temp = head;
    
            if (size != 0){
        
                head = head.next;
                head.pre = null;
                size --;
            }
    
            return temp;
    
        }
    
        /**
         * 删除尾节点
         * @return
         */
        public Object deleteTail(){
        
    
            Node temp = tail;
    
            if (size != 0){
        
                tail = tail.pre;
                size --;
            }
    
            return temp;
        }
    
    
        /**
         * 获取节点个数
         * @return
         */
       public int getSize(){
        
            return size;
       }
    
    
        /**
         * 显示节点信息
         */
        public void display(){
        
            if(size >0){
        
                Node node = head;
                int tempSize = size;
                if(tempSize == 1){
        //当前链表只有一个节点
                    System.out.println("["+node.object+"]");
                    return; }
                while(tempSize>0){
        
                    if(node.equals(head)){
        
                        System.out.print("["+node.object+"->");
                    }else if(node.next == null){
        
    
                        System.out.print(node.object+"]");
                    }else{
        
                        System.out.print(node.object+"->");
                    }
                    node = node.next;
                    tempSize--;
                }
                System.out.println(); }else{
        //如果链表一个节点都没有，直接打印[]
                System.out.println("[]");
            }
        }
    
    }

#### 有序链表 ####

前面的链表实现插入数据都是无序的，在有些应用中需要链表中的数据有序，这称为有序链表。  
在有序链表中，数据是按照关键值有序排列的。一般在大多数需要使用有序数组的场合也可以使用有序链表。有序链表优于有序数组的地方是插入的速度(因为元素不需要移动)，另外链表可以扩展到全部有效的使用内存，而数组只能局限于一个固定的大小中。

public class OrderLinkedList {
        
      private Node head;
      
      private class Node{
        
          private int data;
          private Node next;
          public Node(int data){
        
              this.data = data;
      } 
    }
      public OrderLinkedList(){
        
          head = null;
    }
    //插入节点，并按照从小打到的顺序排列 public void insert(int value){
        
          Node node = new Node(value);
          Node pre = null;
          Node current = head;
          while(current != null && value > current.data){
        
              pre = current;
              current = current.next;
          }
          if(pre == null){
        
              head = node;
              head.next = current;
          }else{
        
              pre.next = node;
              node.next = current;
          }
    }
    //删除头节点
    public void deleteHead(){
        
          head = head.next;
      }
      public void display(){
        
          Node current = head;
          while(current != null){
        
              System.out.print(current.data+" ");
              current = current.next;
          }
          System.out.println("");
      }
    }

在有序链表中插入和删除某一项最多需要O(N)次比较，平均需要O(N/2)次，因为必须沿着链表上一 步一步走才能找到正确的插入位置，然而可以最快速度删除最值，因为只需要删除表头即可，如果一个 应用需要频繁的存取最小值，且不需要快速的插入，那么有序链表是一个比较好的选择方案。比如优先 级队列可以使用有序链表来实现

#### 总结 ####

上面我们讲了各种链表，每个链表都包括一个LinikedList对象和许多Node对象，LinkedList对象通常 包含头和尾节点的引用，分别指向链表的第一个节点和最后一个节点。而每个节点对象通常包含数据部 分data，以及对上一个节点的引用prev和下一个节点的引用next，只有下一个节点的引用称为单向链 表，两个都有的称为双向链表。next值为null则说明是链表的结尾，如果想找到某个节点，我们必须从 第一个节点开始遍历，不断通过next找到下一个节点，直到找到所需要的。栈和队列都是ADT，可以用 数组来实现，也可以用链表实现

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTEzNDMw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200608185221525.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTEzNDMw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTEzNDMw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2020060818533319.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTEzNDMw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTEzNDMw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200608185357419.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTEzNDMw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTEzNDMw_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200608185755774.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTEzNDMw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTEzNDMw_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200608185945170.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NTEzNDMw,size_16,color_FFFFFF,t_70