博客
关于我
强烈建议你试试无所不能的chatGPT，快点击我
数据结构与算法 | 线性表 —— 链表
阅读量：7290 次
发布时间：2019-06-30

本文共 19338 字，大约阅读时间需要 64 分钟。

原文链接：

链表

定义

逻辑结构上一个挨一个的数据，在实际存储时，并没有像顺序表那样也相互紧挨着。恰恰相反，数据随机分布在内存中的各个位置，这种存储结构称为线性表的链式存储。

由于分散存储，为了能够体现出数据元素之间的逻辑关系，每个数据元素在存储的同时，要配备一个指针，用于指向它的直接后继元素，即每一个数据元素都指向下一个数据元素（最后一个指向NULL(空)）。这种结构成为 "单向链表"。

在单向链表的基础上，给各个结点额外配备一个指针变量，用于指向每个结点的直接前趋元素。这样的链表被称为“双向链表”或者“双链表”。

当单向链表的尾部数据指向头部数据时，就构成了单向循环链表。

当双向链表的头部和尾部相互指向时，就构成了双向循环链表。

单向链表

单向链表在插入元素、删除元素时，需要获取前驱元素，需要从head开始遍历，时间复杂度为O(n)。

根据index查询对应元素，也需要从head开始遍历，时间复杂度为O(n)。

代码实现

package one.wangwei.algorithms.datastructures.list.impl;import one.wangwei.algorithms.datastructures.list.IList;/** * Single Linked List * * @author https://wangwei.one * @date 2018/12/25 */public class SingleLinkedList
    
      implements IList
     
       {    /**     * size     */    private int size = 0;    /**     * head node     */    private Node
      
        head;    /**     * tail node     */    private Node
       
         tail;    /**     * add element     *     * @param element     * @return     */    @Override    public boolean add(T element) {        return addLast(element);    }    /**     * add element at index     *     * @param index     * @param element     * @return     */    @Override    public boolean add(int index, T element) {        if (index < 0 || index > size) {            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);        }        if (index == size) {            return add(element);        } else {            return addBefore(index, element);        }    }    /**     * Add Last element     *     * @param element     * @return     */    private boolean addLast(T element) {        Node
        
          last = tail;        Node
         
           newNode = new Node<>(null, element); tail = newNode; // if linked list is empty if (last == null) { head = newNode; } else { last.next = newNode; } size++; return true; } /** * add element before certain element * * @param index * @param element * @return */ private boolean addBefore(int index, T element) { checkPositionIndex(index); // prev node Node
          
            prev = null; Node
           
             x = head; for (int i = 0; i < index; i++) { prev = x; x = x.next; } // current node Node
            
              current = x; // new node Node
             
               newNode = new Node<>(current, element); // if current node is head if (prev == null) { head = newNode; } else { prev.next = newNode; } size++; return true; } /** * remove element * * @param element * @return */ @Override public boolean remove(T element) { Node
              
                prev = null; Node
               
                 x = head; if (element == null) { while (x != null && x.element != null) { prev = x; x = x.next; } } else { while (x != null && !x.element.equals(element)) { prev = x; x = x.next; } } // if this linked is null OR don't find element if (x == null) { return false; } Node
                
                  next = x.next; // if delete node is head if (prev == null) { head = next; } else { prev.next = next; } // if delete node is tail if (next == null) { tail = prev; } // for GC x.element = null; x = null; size--; return true; } /** * remove element by index * * @param index * @return */ @Override public T remove(int index) { checkPositionIndex(index); Node
                 
                   prev = null; Node
                  
                    x = head; for (int i = 0; i < index; i++) { prev = x; x = x.next; } // if linked is empty if (x == null) { return null; } Node
                   
                     next = x.next; // if delete node is head if (prev == null) { head = next; } else { prev.next = next; } // if delete node is tail if (next == null) { tail = prev; } size--; return x.element; } /** * set element by index * * @param index * @param element * @return old element */ @Override public T set(int index, T element) { checkPositionIndex(index); Node
                    
                      node = node(index); T oldElement = node.element; node.element = element; return oldElement; } /** * get element by index * * @param index * @return */ @Override public T get(int index) { Node
                     
                       node = node(index); return node == null ? null : node.element; } /** * get element by index * * @param index * @return */ private Node
                      
                        node(int index) { checkPositionIndex(index); Node
                       
                         x = head; for (int i = 0; i < index; i++) { x = x.next; } return x; } /** * check index * * @param index */ private void checkPositionIndex(int index) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size); } } /** * clear list */ @Override public void clear() { for (Node
                        
                          x = head; x != null; ) { Node
                         
                           next = x.next; x.element = null; x.next = null; x = next; } head = tail = null; size = 0; } /** * contain certain element * * @param element */ @Override public boolean contains(T element) { if (element == null) { for (Node
                          
                            x = head; x != null; x = x.next) { if (x.element == null) { return true; } } } else { for (Node
                           
                             x = head; x != null; x = x.next) { if (x.element.equals(element)) { return true; } } } return false; } /** * get list size * * @return */ @Override public int size() { return size; } /** * Linked List Node * * @param 
                            
                              */ private class Node
                             
                               { private Node
                              
                                next; private T element; public Node(Node
                               
                                 next, T element) { this.next = next; this.element = element; } }}复制代码

双向链表

相比于单向链表，双向链表多了一个前驱指针，在查找前驱节点时，时间复杂度降低为了O(1)。

通过index查询，删除某个node节点，时间复杂度都降为了O(1)。代码如下：

代码实现

package one.wangwei.algorithms.datastructures.list.impl;import one.wangwei.algorithms.datastructures.list.IList;/** * Doubly Linked List * * @param 
    
      * @author https://wangwei.one * @date 2018/04/28 */public class DoublyLinkedList
     
       implements IList
      
        {    /**     * size     */    private int size = 0;    /**     * head element     */    private Node
       
         head = null;    /**     * tail element     */    private Node
        
          tail = null;    /**     * add element     *     * @param element     * @return     */    @Override    public boolean add(T element) {        return addLast(element);    }    /**     * add element at index     *     * @param index     * @param element     * @return     */    @Override    public boolean add(int index, T element) {        if (index < 0 || index > size) {            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);        }        if (index == size) {            return add(element);        } else {            return addBefore(element, node(index));        }    }    /**     * Add Last element     *     * @param element     * @return     */    private boolean addLast(T element) {        final Node
         
           last = tail; Node
          
            newNode = new Node<>(last, element, null); tail = newNode; if (last == null) { head = newNode; } else { last.next = newNode; } size++; return true; } /** * add element before certain element * * @param element * @param target * @return */ private boolean addBefore(T element, Node
           
             target) { Node
            
              prev = target.prev; Node
             
               newNode = new Node<>(prev, element, target); target.prev = newNode; if (prev == null) { head = newNode; } else { prev.next = newNode; } size++; return true; } /** * remove node by element * * @param element * @return */ @Override public boolean remove(T element) { if (element == null) { for (Node
              
                x = head; x != null; x = x.next) { if (x.element == null) { unlink(x); return true; } } } else { for (Node
               
                 x = head; x != null; x = x.next) { if (element.equals(x.element)) { unlink(x); return true; } } } return false; } /** * remove node by index * * @param index * @return */ @Override public T remove(int index) { return unlink(node(index)); } /** * get element by index * * @param index * @return */ private Node
                
                  node(int index) { checkPositionIndex(index); if (index < (size >> 1)) { Node
                 
                   x = head; for (int i = 0; i < index; i++) { x = x.next; } return x; } else { Node
                  
                    x = tail; for (int i = size - 1; i > index; i--) { x = x.prev; } return x; } } /** * unlink node * * @param node */ private T unlink(Node
                   
                     node) { final T element = node.element; final Node
                    
                      prev = node.prev; final Node
                     
                       next = node.next; // if unlink is head if (prev == null) { head = next; } else { prev.next = next; // clear prev node.prev = null; } // if unlink is tail if (next == null) { tail = prev; } else { next.prev = prev; node.next = null; } node.element = null; size--; return element; } private void checkPositionIndex(int index) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size); } } /** * set element by index * * @param index * @param element * @return */ @Override public T set(int index, T element) { checkPositionIndex(index); Node
                      
                        oldNode = node(index); T oldElement = oldNode.element; oldNode.element = element; return oldElement; } /** * get element by index * * @param index * @return */ @Override public T get(int index) { Node
                       
                         node = node(index); return node == null ? null : node.element; } /** * clear list */ @Override public void clear() { for (Node
                        
                          x = head; x != null; ) { Node
                         
                           next = x.next; x.element = null; x.next = null; x.prev = null; x = next; } head = tail = null; size = 0; } /** * contain certain element * * @param element */ @Override public boolean contains(T element) { if (element == null) { for (Node
                          
                            x = head; x != null; x = x.next) { if (x.element == null) { return true; } } } else { for (Node
                           
                             x = head; x != null; x = x.next) { if (element.equals(x.element)) { return true; } } } return false; } /** * get list size * * @return */ @Override public int size() { return size; } /** * node * * @param 
                            
                              */ private class Node
                             
                               { private T element; private Node
                              
                                prev; private Node
                               
                                 next; public Node(Node
                                
                                  prev, T element, Node
                                 
                                   next) { this.element = element; this.prev = prev; this.next = next; } }}复制代码

单向循环链表

与单向链表一样，在寻找前驱节点时，需要遍历整个链表，时间复杂度为O(n).

在第一次添加元素时，特别注意，head与tail为同一节点，并且需要自指向。

package one.wangwei.algorithms.datastructures.list.impl;import one.wangwei.algorithms.datastructures.list.IList;/** * Singly Circular Linked List * * @param 
    
      * @author https://wangwei.one * @date 2018/05/03 */public class SinglyCircularLinkedList
     
       implements IList
      
        {    /**     * size     */    private int size = 0;    /**     * head node     */    private Node
       
         head = null;    /**     * tail node     */    private Node
        
          tail = null;    /**     * add element     *     * @param element     * @return     */    @Override    public boolean add(T element) {        return addLast(element);    }    /**     * add element at index     *     * @param index     * @param element     * @return     */    @Override    public boolean add(int index, T element) {        if (index < 0 || index > size) {            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);        }        if (index == size) {            return add(element);        } else {            return addBefore(index, element);        }    }    /**     * Add Last element     *     * @param element     * @return     */    private boolean addLast(T element) {        final Node
         
           last = tail; Node
          
            newElement = new Node<>(element, head); tail = newElement; if (last == null) { head = newElement; // we need linked itself when add an element first tail.next = head; } else { last.next = newElement; } size++; return true; } /** * add element before certain element * * @param element * @param element * @return */ private boolean addBefore(int index, T element) { checkPositionIndex(index); // prev node, start with tail Node
           
             prev = tail; Node
            
              x = head; for (int i = 0; i < index; i++) { prev = x; x = x.next; } // current node Node
             
               current = x; // new node Node
              
                newNode = new Node<>(element, current); if (index == 0) { head = newNode; } prev.next = newNode; size++; return true; } /** * remove node by element * * @param element * @return */ @Override public boolean remove(T element) { // start with tail Node
               
                 prev = tail; // start with head Node
                
                  x = head; // start with index -1 int prevIndex = -1; for (int i = 0; i < size; i++) { if (element == null && x.element == null) { break; } if (element != null && element.equals(x.element)) { break; } prev = x; x = x.next; prevIndex = i; } // if this linked list is empty if (x == null) { return false; } // if don't match element if (prevIndex == size - 1) { return false; } Node
                 
                   next = x.next; // if delete node is head if (prevIndex == -1) { head = next; } // if delete node is tail if (prevIndex == size - 2) { tail = prev; } prev.next = next; size--; if (size == 0) { head = tail = null; } // for GC x = null; return true; } /** * remove element by index * * @param index * @return */ @Override public T remove(int index) { checkPositionIndex(index); Node
                  
                    prev = tail; Node
                   
                     x = head; for (int i = 0; i < index; i++) { prev = x; x = x.next; } // if linked is empty if (x == null) { return null; } Node
                    
                      next = x.next; // if delete node is head if (index == 0) { head = next; } // if delete node is tail if (index == size - 1) { tail = prev; } prev.next = next; size--; if (size == 0) { head = tail = null; } return x.element; } /** * get element by index * * @param index * @return */ private Node
                     
                       node(int index) { checkPositionIndex(index); Node
                      
                        x = head; for (int i = 0; i < index; i++) { x = x.next; } return x; } private void checkPositionIndex(int index) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size); } } /** * set element by index * * @param index * @param element * @return */ @Override public T set(int index, T element) { checkPositionIndex(index); Node
                       
                         oldNode = node(index); T oldElement = oldNode.element; oldNode.element = element; return oldElement; } /** * get element by index * * @param index * @return */ @Override public T get(int index) { return node(index).element; } /** * clear list element */ @Override public void clear() { for (Node
                        
                          x = head; x != null; ) { Node
                         
                           next = x.next; x.element = null; x.next = null; x = next; } head = tail = null; size = 0; } /** * contain certain element * * @param element */ @Override public boolean contains(T element) { if (head == null) { return false; } Node
                          
                            x = head; for (int i = 0; i < size; i++) { if (element == null && x.element == null) { return true; } if (element != null && element.equals(x.element)) { return true; } x = x.next; } return false; } /** * get list size * * @return */ @Override public int size() { return size; } /** * Node * * @param 
                           
                             */ private class Node
                            
                              { private T element; private Node
                             
                               next; public Node(T element, Node
                              
                                next) { this.element = element; this.next = next; } }}复制代码

双向循环链表

双向循环链表相比单向循环链表，降低了查找前驱节点的复杂度，时间复杂度为O(1).

同样第一次添加元素时，head与tail为同一元素，需要自指向。

package one.wangwei.algorithms.datastructures.list.impl;import one.wangwei.algorithms.datastructures.list.IList;/** * Doubly circular linked list * * @author https://wangwei.one * @date 2018/12/21 */public class DoublyCircularLinkedList
    
      implements IList
     
       {    /**     * size     */    private int size;    /**     * head node     */    private Node
      
        head;    /**     * tail node     */    private Node
       
         tail;    /**     * add element     *     * @param element     * @return     */    @Override    public boolean add(T element) {        return addLast(element);    }    /**     * add element at index     *     * @param index     * @param element     * @return     */    @Override    public boolean add(int index, T element) {        if (index < 0 || index > size) {            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);        }        if (index == size) {            return add(element);        } else {            return addBefore(index, element);        }    }    /**     * Add last element     *     * @param element     * @return     */    private boolean addLast(T element) {        Node
        
          last = tail;        Node
         
           newNode = new Node<>(element, last, head); tail = newNode; // add element at first if (last == null) { head = newNode; tail.next = head; } else { last.next = newNode; } head.prev = tail; size++; return true; } /** * add element before certain element * * @param index * @param element * @return */ private boolean addBefore(int index, T element) { Node
          
            target = node(index); Node
           
             prev = target.prev; Node
            
              newNode = new Node<>(element, prev, target); prev.next = newNode; target.prev = newNode; if (index == 0) { head = newNode; } size++; return true; } /** * remove element * * @param element * @return */ @Override public boolean remove(T element) { // start with head Node
             
               x = head; // start with index -1 int prevIndex = -1; for (int i = 0; i < size; i++) { if (element == null && x.element == null) { break; } if (element != null && element.equals(x.element)) { break; } x = x.next; prevIndex = i; } // if this linked list is empty if (x == null) { return false; } // if don't match element if (prevIndex == size - 1) { return false; } Node
              
                prev = x.prev; Node
               
                 next = x.next; // if delete node is head if (prevIndex == -1) { head = next; } // if delete node is tail if (prevIndex == size - 2) { tail = prev; } prev.next = next; next.prev = prev; size--; if (size == 0) { head = tail = null; } // for GC x = null; return true; } /** * remove element by index * * @param index * @return */ @Override public T remove(int index) { checkPositionIndex(index); Node
                
                  x = head; for (int i = 0; i < index; i++) { x = x.next; } // if linked is empty if (x == null) { return null; } Node
                 
                   prev = x.prev; Node
                  
                    next = x.next; // if delete node is head if (index == 0) { head = next; } // if delete node is tail if (index == size - 1) { tail = prev; } prev.next = next; next.prev = prev; size--; if (size == 0) { head = tail = null; } return x.element; } private void checkPositionIndex(int index) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size); } } /** * set element by index * * @param index * @param element * @return old element */ @Override public T set(int index, T element) { Node
                   
                     oldNode = node(index); T oldElement = oldNode.element; oldNode.element = element; return oldElement; } /** * get element by index * * @param index * @return */ @Override public T get(int index) { return node(index).element; } /** * get element by index * * @param index * @return */ private Node
                    
                      node(int index) { checkPositionIndex(index); if (index < (size >> 1)) { Node
                     
                       x = head; for (int i = 0; i < index; i++) { x = x.next; } return x; } else { Node
                      
                        x = tail; for (int i = size - 1; i > index; i--) { x = x.prev; } return x; } } /** * clear list */ @Override public void clear() { for (Node
                       
                         x = head; x != null; ) { Node
                        
                          next = x.next; x.element = null; x.next = null; x = next; } head = tail = null; size = 0; } /** * contain certain element * * @param element * @return */ @Override public boolean contains(T element) { if (head == null) { return false; } Node
                         
                           x = head; for (int i = 0; i < size; i++) { if (element == null && x.element == null) { return true; } if (element != null && element.equals(x.element)) { return true; } x = x.next; } return false; } /** * get list size * * @return */ @Override public int size() { return size; } /** * Node * * @param 
                          
                            */ private class Node
                           
                             { private T element; private Node
                            
                              prev; private Node
                             
                               next; public Node(T element, Node
                              
                                prev, Node
                               
                                 next) { this.element = element; this.prev = prev; this.next = next; } }}复制代码

ArrayList vs LinkedList

ArrayList LinkedList
插入&
删除		 O(n) O(1)
随机访问 O(1) O(n)
优点 连续的内存空间，可以借助CPU的预取机制 内存不连续，天然支持动态扩容
缺点 无法存储大数据，数组扩容耗性能 频繁地插入删除操作，会导致内存碎片的增加，导致频繁的GC

参考资料

  • 《》

转载地址：http://jpcjm.baihongyu.com/

你可能感兴趣的文章
磁盘的基础知识——扇区、柱面、磁道、族
查看>>
伪链接的差异
查看>>
火狐和谷歌浏览器对js事件兼容问题
查看>>
2017-05 CentOS7 Docker的安装与卸载
查看>>
django静态文件配置
查看>>
HashTable的使用和原理
查看>>
ssm框架中的配置文件
查看>>
ADO.NET操作数据库（一）
查看>>
Android模拟器编译和模拟
查看>>
json数据类型直接赋值给相应的对象
查看>>
CentOS 7 修改时区
查看>>
bootstrap3 - 自适应导航
查看>>
中国与印度软件工程师之比较
查看>>
Kylin中的cube构建过程
查看>>
【自用】Android | Bitmap的水平&垂直翻转
查看>>
打印GC日志 的JVM参数设置
查看>>
Dos命令之Tree命令详解
查看>>
IT人士 不能一辈子靠技术生存
查看>>
JMS在Spring框架下的应用
查看>>
设计模式在JS编程中的应用
查看>>
喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！
当前时间: 2025-02-15 08:32:00   当前IP: 3.145.212.129   联系邮箱:javaeecc@qq.com     Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2
强烈建议你试试无所不能的CHAT-GPT，快点击我
强烈建议你试试无所不能的CHAT-GPT，快点击我