美文网首页
数据结构与算法之链表(二)单链表的基本实现

数据结构与算法之链表(二)单链表的基本实现

作者: kakaxicm | 来源:发表于2018-05-22 17:36 被阅读0次

    引言

    创建顺序表时必须分配一块连续的内存存储空间，而当顺序表内部数组的容量不足时，则必须创建一个新的数组，然后把原数组的的元素复制到新的数组中，这将浪费大量的时间。而在插入或删除元素时，可能需要移动数组中的元素，这也将消耗一定的时间。而链表在初始化时仅需要分配一个元素的存储空间，它通过节点逻辑上的前赴后继关系来访问元素，内存分配不连续，所以增加和删除操作不用考虑扩容和元素迁移的问题。由于存储非连续，导致它的增删改查都不能像顺序表那样直接根据索引来操作，但是这些缺点jdk的List容器实现都进行了优化，这个我们以后再详细分析。下面是单链表的结构示意图:


    单链表结构.png

    每一个节点都包含数据域data和指针域next,data表示节点承载的元素，next表示后继节点指针(即引用),它表明了单链表的节点之间的“后继关系”，只要拿到链表的头节点就可以访问整个链表了。

    基本实现

    1.单链表接口

    package List.singlelist;

/**
 * Created by chenming on 2018/5/22
 */
public interface ISingleList<T> {
    int size();//大小

    boolean isEmpty();//是否为空

    void clear();//清空

    boolean contains(T item);//是否包含某元素

    boolean add(T item);//追加元素

    T get(int index);//获取元素

    T set(int index, T item);//修改元素

    void add(int index, T item);//指定位置前添加元素

    T remove(int index);//删除元素
}

    2.具体实现:
    1>单链表节点类型:包含数据域data和指针域next

    package List.singlelist;

/**
 * Created by chenming on 2018/5/22
 * 单链表节点
 */
public class SNode<T> {
    public T data;//数据域
    public SNode<T> next;//地址域

    public SNode(T data){
        this.data=data;
    }

    public SNode(T data,SNode<T> next){
        this.data=data;
        this.next=next;
    }
}

    2>成员属性:头结点

    /**
 * Created by chenming on 2018/5/22
 */
public class SingleList<T> implements ISingleList<T> {

    protected SNode<T> headNode; //带数据头结点

    public SingleList() {
    }
    ....
}

    3>是否为空与获得长度:获得长度是通过从头结点遍历到尾节点得到，后面的增删改查操作都需要类似的遍历

     /*
  * 是否为空
  *
  * @return
  */
 @Override
  public boolean isEmpty() {
      return headNode == null;
  }
 /**
   * 获取链表长度
   *
   * @return
   */
  @Override
  public int size() {
      int len = 0;
      SNode<T> p = headNode;
      while (p != null) {
          len++;
          p = p.next;
      }
      return len;
  }

    4>查找和修改元素:都是先找到指定位置的节点然后做操作.

       /**
     * 查找元素
     *
     * @param index
     * @return
     */
    @Override
    public T get(int index) {
       //边界条件判断
        if (isEmpty()) {
            return null;
        }
       //数组下限越界
        if (index < 0) {
            throw new IndexOutOfBoundsException();
        }
        int scanIndex = 0;//扫描索引
        SNode<T> p = headNode;
       //遍历到目标位置
        while (p != null && scanIndex < index) {
            scanIndex++;
            p = p.next;
        }
        if (p != null) {
            return p.data;
        } else {//p为null表示遍历到链表结尾，说明index越界
            throw new IndexOutOfBoundsException();
        }
    }
   /**
     * 设置元素，返回旧的元素
     *
     * @param index
     * @param item
     * @return
     */
    @Override
    public T set(int index, T item) {
        //先判断是否为空
        if (isEmpty()) {
            return null;
        }
        //index校验
        if (index < 0) {
            throw new IndexOutOfBoundsException();
        }
        //游到指定index
        int scanIndex = 0;//扫描索引
        SNode<T> p = headNode;
        while (p != null && scanIndex < index) {
            scanIndex++;
            p = p.next;
        }
        if (p != null) {
            T oldData = p.data;
            p.data = item;//设置新值
            return oldData;
        } else {//遍历到链表结尾表明index越界
            throw new IndexOutOfBoundsException();
        }
    }

    5>增加元素,分三种情况：
    1)头部插入节点:当头节点为空或者插入位置为0时，新节点插入表头，需要做下面的操作:(1)新建节点;(2)节点指向当前表头;(3)表头节点指向新节点.如下图


    表头插入元素.png

    代码表示如下:

       SNode<T> newNode = new SNode<>(item);
   newNode.next = headNode;
   headNode = newNode;

    2)中间和尾部插入元素二者虽然位置不同单逻辑一样，这里统一处理:
    (1)新建节点(2)新建节点的后继节点指定为插入位置前一节点的后继节点(即新节点连接后继链表)(3)插入位置前一节点的后继节点指定为新节点(即断开旧连接，连接新节点)。操作示意图如下:


    节点插入过程.png

    代码表示如下:

      //尾部和中间插入
  SNode<T> newNode = new SNode<>(item);
  newNode.next = prev.next;//新节点连接后节点
  prev.next = newNode;//前节点链接后节点

    当插入链表末尾时,pre.next为空，上面的代码依然可以实现尾部添加。
    插入元素的完整代码:

        @Override
    public void add(int index, T item) {
        /**
         *
         * 1.头部插入新节点
         * 2.中间插入新节点
         * 3.末尾插入新节点
         */
        if (item == null) {
            return;
        }

        if (index < 0) {
            throw new IndexOutOfBoundsException();
        }

        //头部插入
        if (isEmpty() || index == 0) {
            SNode<T> newNode = new SNode<>(item);
            newNode.next = headNode;
            headNode = newNode;
        } else {
            //中部或者尾部插入
            SNode<T> prev = headNode;
            int scanIndex = 0;//扫描索引
            //找到插入位置的前节点
            while (prev.next != null && scanIndex < index - 1) {
                scanIndex++;
                prev = prev.next;//游标前移
            }
            //遍历到链表结尾,由于追加可以追加到尾部，所以这里对index的限定为size大小
            if (prev.next == null && scanIndex < index - 1) {
                throw new IndexOutOfBoundsException();
            }
            //尾部和中间插入
            SNode<T> newNode = new SNode<>(item);
            newNode.next = prev.next;//新节点连接后节点
            prev.next = newNode;//前节点链接后节点
        }
    }
   /**
     * 尾部添加元素
     *
     * @param item
     * @return
     */
    @Override
    public boolean add(T item) {
        /**
         *
         * 1.头部插入新节点
         * 2.中间插入新节点
         * 3.末尾插入新节点
         */
        if (item == null) {
            return false;
        }

        //头部插入
        if (isEmpty()) {
            SNode<T> newNode = new SNode<>(item);
            newNode.next = headNode;
            headNode = newNode;
        } else {
            //中部或者尾部插入
            SNode<T> prev = headNode;
            while (prev.next != null) {
                prev = prev.next;//游标前移
            }
            //尾部追加新节点
            SNode<T> newNode = new SNode<>(item);
            prev.next = newNode;//连接新节点
        }
        return true;
    }

    6>删除元素的逻辑和增加类似，主要是找到删除位置做断开节点操作.
    1)如果是删除头结点:则将头结点指向下一节点即可;
    2)如果是删除中间节点或者尾节点,则将目标位置的节点的前节点的后继指针指向当前节点的后继指针即可。删除节点的逻辑比较简单这里就不上示意图了，直接看代码:

       /**
     * 删除头结点
     * 删除中间节点
     *
     * @param index
     * @return
     */
    @Override
    public T remove(int index) {
        if (isEmpty()) {
            return null;
        }
        if (index < 0) {
            throw new IndexOutOfBoundsException();
        }

        T old = null;
        if (index == 0) {
            //删除头结点
            old = headNode.data;
            headNode = headNode.next;
            return old;
        } else {
            //中部或者尾部删除
            SNode<T> prev = headNode;
            int scanIndex = 0;//扫描索引
            //查找目标位置的前一个节点
            while (prev.next != null && scanIndex < index - 1) {
                scanIndex++;
                prev = prev.next;//游标前移
            }
            //遍历到链表尾部，scanIndex仍然小于目标索引,所以上限越界
            if (prev.next == null && scanIndex < index) {
                throw new IndexOutOfBoundsException();
            }
            //需要删除的节点
            SNode<T> targetNode = prev.next;
            if (targetNode != null) {
                old = targetNode.data;
                prev.next = targetNode.next;
                targetNode = null;
            }
        }
        return old;
    }

    7>清空和判断是否包含元素操作:

        @Override
    public void clear() {
        headNode = null;
    }

    @Override
    public boolean contains(T item) {
        if (item == null) {
            return false;
        }

        if (isEmpty()) {
            return false;
        }

        SNode<T> node = headNode;
        while (node != null) {
            T data = node.data;
            if (data.equals(item)) {
                return true;
            }
            node = node.next;
        }
        return false;
    }

    全部代码实现:

    package List.singlelist;

/**
 * Created by chenming on 2018/5/22
 */
public class SingleList<T> implements ISingleList<T> {

    protected SNode<T> headNode; //带数据头结点

    public SingleList() {
    }

    public SingleList(SNode<T> headNode) {
        this.headNode = headNode;
    }

    /**
     * 是否为空
     *
     * @return
     */
    @Override
    public boolean isEmpty() {
        return headNode == null;
    }

    /**
     * 获取链表长度
     *
     * @return
     */
    @Override
    public int size() {
        int len = 0;
        SNode<T> p = headNode;
        while (p != null) {
            len++;
            p = p.next;
        }
        return len;
    }

    /**
     * 查找元素
     *
     * @param index
     * @return
     */
    @Override
    public T get(int index) {
        if (isEmpty()) {
            return null;
        }

        if (index < 0) {
            throw new IndexOutOfBoundsException();
        }
        int scanIndex = 0;//扫描索引
        SNode<T> p = headNode;
        while (p != null && scanIndex < index) {
            scanIndex++;
            p = p.next;
        }
        if (p != null) {
            return p.data;
        } else {//遍历到链表结尾表明index越界
            throw new IndexOutOfBoundsException();
        }
    }

    /**
     * 设置元素，返回旧的元素
     *
     * @param index
     * @param item
     * @return
     */
    @Override
    public T set(int index, T item) {
        //先判断是否为空
        if (isEmpty()) {
            return null;
        }
        //index校验
        if (index < 0) {
            throw new IndexOutOfBoundsException();
        }
        //游到指定index
        int scanIndex = 0;//扫描索引
        SNode<T> p = headNode;
        while (p != null && scanIndex < index) {
            scanIndex++;
            p = p.next;
        }
        if (p != null) {
            T oldData = p.data;
            p.data = item;//设置新值
            return oldData;
        } else {//遍历到链表结尾表明index越界
            throw new IndexOutOfBoundsException();
        }

    }

    @Override
    public void add(int index, T item) {
        /**
         *
         * 1.头部插入新节点
         * 2.中间插入新节点
         * 3.末尾插入新节点
         */
        if (item == null) {
            return;
        }

        if (index < 0) {
            throw new IndexOutOfBoundsException();
        }

        //头部插入
        if (isEmpty() || index == 0) {
            SNode<T> newNode = new SNode<>(item);
            newNode.next = headNode;
            headNode = newNode;
        } else {
            //中部或者尾部插入
            SNode<T> prev = headNode;
            int scanIndex = 0;//扫描索引
            while (prev.next != null && scanIndex < index - 1) {
                scanIndex++;
                prev = prev.next;//游标前移
            }
            //遍历到链表结尾,由于追加可以追加到尾部，所以这里对index的限定为size大小
            if (prev.next == null && scanIndex < index - 1) {
                throw new IndexOutOfBoundsException();
            }
            //尾部和中间插入
            SNode<T> newNode = new SNode<>(item);
            newNode.next = prev.next;//新节点连接后节点
            prev.next = newNode;//前节点链接后节点
        }
    }

    /**
     * 删除头结点
     * 删除中间节点
     *
     * @param index
     * @return
     */
    @Override
    public T remove(int index) {
        if (isEmpty()) {
            return null;
        }
        if (index < 0) {
            throw new IndexOutOfBoundsException();
        }

        T old = null;
        if (index == 0) {
            //删除头结点
            old = headNode.data;
            headNode = headNode.next;
            return old;
        } else {
            //中部或者尾部删除
            SNode<T> prev = headNode;
            int scanIndex = 0;//扫描索引
            //查找目标位置的前一个节点
            while (prev.next != null && scanIndex < index - 1) {
                scanIndex++;
                prev = prev.next;//游标前移
            }
            //遍历到链表尾部，scanIndex仍然小于目标索引,所以上限越界
            if (prev.next == null && scanIndex < index) {
                throw new IndexOutOfBoundsException();
            }
            //需要删除的节点
            SNode<T> targetNode = prev.next;
            if (targetNode != null) {
                old = targetNode.data;
                prev.next = targetNode.next;
                targetNode = null;
            }
        }
        return old;
    }

    @Override
    public void clear() {
        headNode = null;
    }

    @Override
    public boolean contains(T item) {
        if (item == null) {
            return false;
        }

        if (isEmpty()) {
            return false;
        }

        SNode<T> node = headNode;
        while (node != null) {
            T data = node.data;
            if (data.equals(item)) {
                return true;
            }
            node = node.next;
        }
        return false;
    }

    /**
     * 尾部添加元素
     *
     * @param item
     * @return
     */
    @Override
    public boolean add(T item) {
        /**
         *
         * 1.头部插入新节点
         * 2.中间插入新节点
         * 3.末尾插入新节点
         */
        if (item == null) {
            return false;
        }

        //头部插入
        if (isEmpty()) {
            SNode<T> newNode = new SNode<>(item);
            newNode.next = headNode;
            headNode = newNode;
        } else {
            //中部或者尾部插入
            SNode<T> prev = headNode;
            while (prev.next != null) {
                prev = prev.next;//游标前移
            }
            //尾部追加新节点
            SNode<T> newNode = new SNode<>(item);
            prev.next = newNode;//连接新节点
        }
        return true;
    }
}

    总结:本文主要学习了单链表的操作，但是单链表只是表明了节点间"后继"的关系,没有"前赴"关系，遍历只能单向遍历，效率较低。后面我们将继续学习双向链表的基本实现。代码地址https://github.com/kakaxicm/AlgorithLearning

    相关文章

      网友评论

          本文标题：数据结构与算法之链表(二)单链表的基本实现

          本文链接：https://www.haomeiwen.com/subject/pbxkjftx.html

          延伸阅读

          深度阅读

          • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

          栏目导航

          热点阅读

          关于我们|服务条款|联系我们|数据结构与算法之链表(二)单链表的基本实现|投稿指南|网站地图|RSS订阅|排版工具|手机版

          提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

          Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

          备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

          本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

          所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！