Java数据结构-线性表之单链表LinkedList

喜欢ヅ旅行 2022-08-02 11:53 270阅读 0赞

线性表的链式存储结构，也称之为**链式表**，链表；链表的**存储单元可以连续也可以不连续**。  
链表中的节点包含数据域和指针域，数据域为存储数据元素信息的域，指针域为存储直接后继位置（一般称为指针）的域。

注意一个头结点和头指针的区别：  
头指针：

*  指向链表的第一个节点的指针，若链表有头结点，则是指向头结点的指针；
 *  头指针具有标识作用，所以常用头指针作为链表的名字；
 *  不论链表是否为空，头指针都不为空；
 *  是链表的必要元素。

头结点：

*  头结点是为了操作的统一和方便而设立的，放在第一个元素节点的前面，其数据域一般无意义，也可以存放链表的长度；
 *  头结点不是链表的必要元素。

这里先讲讲单链表吧，其他的后面再讲。  
无头结点的链表  
![.jpg][]  
有头结点的链表  
![.jpg 1][]  
空链表  
![.jpg 2][]

我试着用Java写了一个LinkedList的代码，如下：

package com.phn.datestructure;
    
    /**
     * @author 潘海南
     * @Email 1016593477@qq.com
     * @TODO 链式表
     * @date 2015年7月18日
     */
    public class FOLinkedList<E> {
        
        //  单链表的头结点
        private FOLinkedNode<E> header = null;
        //  单链表的长度
        private int size;
    
        /**
         * @TODO 默认的无参构造函数
         */
        public FOLinkedList() {
            super();
            this.header = new FOLinkedNode<E>();
            this.setSize();
        }
        /**
         * @TODO 单链表添加元素
         * @param e 数据元素类型
         * @return true
         */
        public boolean add(E e) {
            FOLinkedNode<E> node = new FOLinkedNode<E>(e);
            if (header.getE() == null) {
                header.setE(e);
            } else {
                FOLinkedNode<E> lastNode = this.last(this.header);
                lastNode.addNext(node);
            }
    
            this.size++;
            return true;
        }
        /**
         * @TODO 单链表插入元素
         * @param index 插入位置
         * @param e 数据元素类型
         * @return true
         */
        public boolean insert(int index,E e) {
            FOLinkedNode<E> node = new FOLinkedNode<E>(e);
            FOLinkedNode<E> preNode = this.get(index - 1);
            node.addNext(preNode.next);
            preNode.addNext(node);
            this.size++;
            return true;
        }
        /**
         * @TODO 单链表删除元素
         * @param index 将要删除的元素的索引位置
         * @return E 删除的元素
         */
        public FOLinkedNode<E> remove(int index){
            FOLinkedNode<E> preNode = this.get(index-1);
            FOLinkedNode<E> node = preNode.next;
            preNode.addNext(preNode.next.next);
            node.addNext(null);
            this.size--;
            return node;
        }
        /**
         * @TODO 根据元素索引位置获取元素
         * @param index 元素的索引位置
         * @return E 元素e
         */
        public FOLinkedNode<E> get(int index) {
            validateIndex(index);
            FOLinkedNode<E> temp = this.header;
            int i = 0;
            while (i < index - 1) {
                if (temp != null) {
                    temp = temp.next;
                    i++;
                } else {
                    throw new RuntimeException("节点空值错误");
                }
            }
            return temp;
        }
        /**
         * @TODO 将单链表中索引位置为i的元素修改为元素e
         * @param index 元素的索引位置
         * @param e 需要修改成的元素
         * @return true 修改成功标志
         */
        public boolean set(int index, E e){
            validateIndex(index);
            FOLinkedNode<E> oldNode = this.get(index);
            oldNode.setE(e);
            return true;
        }
        /**
         * @TODO 验证所给索引位置是否合法
         * @param index 给出的索引位置
         */
        private void validateIndex(int index) {
            if (index > this.size || index < 0) {
                throw new RuntimeException("索引错误：" + index);
            }
        }
        /**
         * @TODO 获取单链表的最后一个节点
         * @param header 单链表的头结点
         * @return node 单链表的最后一个节点
         */
        private FOLinkedNode<E> last(FOLinkedNode<E> header) {
            FOLinkedNode<E> temp = header;
            while (true) {
                if (temp.next == null) {
                    return temp;
                }
                temp = temp.next;
            }
        }
    
        @Override
        public String toString() {
            return "[" + this.NodesToString(this.header) + "]";
        }
        /**
         * @TODO 设置单链表的长度
         * @param header 单链表的头结点
         * @return 单链表的节点字符串序列
         */
        private String NodesToString(FOLinkedNode<E> header) {
            StringBuffer sb = new StringBuffer();
            if (header != null) {
                sb.append(header.getE());
                FOLinkedNode<E> temp = new FOLinkedNode<E>();
                temp = header.next;
                while (temp != null) {
                    sb.append(", " + temp.getE());
                    temp = temp.next;
                }
            }
    
            return sb.toString();
        }
        /**
         * @TODO 设置单链表的长度
         */
        private void setSize() {
            this.size = 0;
        }
        /**
         * @TODO 获取单链表的长度
         * @return size 单链表的长度
         */
        public int size() {
            return this.size;
        }
    }

节点类：

package com.phn.datestructure;
    public class FOLinkedNode<E> {
            private E e;// 结点中存放的数据
    
            FOLinkedNode() {
            }
    
            FOLinkedNode(E e) {
                this.e = e;
            }
    
            FOLinkedNode<E> next;// 用来指向该结点的下一个结点
    
            // 设置下一节点的值
            void addNext(FOLinkedNode<E> node) {
                next = node;
            }
    
            public E getE() {
                return e;
            }
    
            public void setE(E e) {
                this.e = e;
            }
    
            @Override
            public String toString() {
                return "Node [e=" + e + ", next=" + next + "]";
            }
    
        }

这里也讲讲数据元素的插入和删除操作；  
插入操作演示如下：  
![.jpg 3][]  
![.jpg 4][]  
![.jpg 5][]  
代码：

s->next = p->next;
    p->next = s;

这里摘了《大话数据结构》的一段文字解释：  
![.jpg 6][]

删除操作如下图：  
![.jpg 7][]

一句代码：

p->next = p->next->next;

结合上述代码和图例，可以看出单链表的删除和插入操作都是由两部分组成：

1.  遍历查找到需要操作的位置的那个元素；
2.  然后进行插入和删除操作。

下面是摘自《大话数据结构》的分析：  
![.jpg 8][]

单链表的整表创建  
方法有头插法和尾插法；  
头插法：相当于插队的方法。如下图  
![.jpg 9][]

相对于头插法，尾插法更加合理一些。

单链表的整表删除  
下面是摘自《大话数据结构》的分析：  
![.jpg 10][]  
![.jpg 11][]

下面比较一下单链表和顺序表：  
![.jpg 12][]

![1.jpg][]

![2.jpg][]

[.jpg]: http://7xionv.com1.z0.glb.clouddn.com/phn/datastructure/无头结点.jpg
[.jpg 1]: http://7xionv.com1.z0.glb.clouddn.com/phn/datastructure/有头结点.jpg
[.jpg 2]: http://7xionv.com1.z0.glb.clouddn.com/phn/datastructure/空链表.jpg
[.jpg 3]: http://7xionv.com1.z0.glb.clouddn.com/phn/datastructure/单链表插入之前.jpg
[.jpg 4]: http://7xionv.com1.z0.glb.clouddn.com/phn/datastructure/单链表插入之时.jpg
[.jpg 5]: http://7xionv.com1.z0.glb.clouddn.com/phn/datastructure/单链表插入之后.jpg
[.jpg 6]: http://7xionv.com1.z0.glb.clouddn.com/phn/datastructure/单链表插入解释.jpg
[.jpg 7]: http://7xionv.com1.z0.glb.clouddn.com/phn/datastructure/单链表删除图例.jpg
[.jpg 8]: http://7xionv.com1.z0.glb.clouddn.com/phn/datastructure/单链表时间复杂度分析.jpg
[.jpg 9]: http://7xionv.com1.z0.glb.clouddn.com/phn/datastructure/头插法演示.jpg
[.jpg 10]: http://7xionv.com1.z0.glb.clouddn.com/phn/datastructure/单链表整表删除分析.jpg
[.jpg 11]: http://7xionv.com1.z0.glb.clouddn.com/phn/datastructure/单链表整表删除代码.jpg
[.jpg 12]: http://7xionv.com1.z0.glb.clouddn.com/phn/datastructure/单链表和顺序表比较.jpg
[1.jpg]: http://7xionv.com1.z0.glb.clouddn.com/phn/datastructure/单链表和顺序表比较分析1.jpg
[2.jpg]: http://7xionv.com1.z0.glb.clouddn.com/phn/datastructure/单链表和顺序表比较分析2.jpg