Java数据结构（线性表）详解

线性表的链式存储与实现

实现线性表的另一种方法是链式存储，即用指针将存储线性表中数据元素的那些单元依次串联在一起。这种方法避免了在数组中用连续的单元存储元素的缺点，因而在执行插入或 删除运算时，不再需要移动元素来腾出空间或填补空缺。然而我们为此付出的代价是，需要在每个单元中设置指针来表示表中元素之间的逻辑关系，因而增加了额外的存储空间的开销.

单链表

链表是一系列的存储数据元素的单元通过指针串接起来形成的，因此每个单元至少有两个域，一个域用于数据元素的存储，另一个域是指向其他单元的指针。这里具有一个数据域和多个指针域的存储单元通常称为结点（node）.

结点接口

package com.wjy.Data_Structure.linearlist.common;
public interface Node {
  /**
   * 获取结点数据域
   *
   * @return
   */
  public Object getData();
  /**
   * 设置结点数据域
   *
   * @param obj
   */
  public void setData(Object obj);
}

单链表结点定义

package com.wjy.Data_Structure.linearlist.common;
//单链表结点定义
public class SLNode implements Node {
  private Object element;
  private SLNode next;
  public SLNode() {
  }
  public SLNode(Object ele, SLNode next) {
    this.element = ele;
    this.next = next;
  }
  public SLNode getNext() {
    return next;
  }
  public void setNext(SLNode next) {
    this.next = next;
  }
  /******** Methods of Node Interface **********/
  @Override
  public Object getData() {
    return element;
  }
  @Override
  public void setData(Object obj) {
    element = obj;
  }
}

线性表的单链表实现

在使用单链表实现线性表的时候，为了使程序更加简洁，我们通常在单链表的前面添 加一个哑元结点，也称为头结点。在头结点中不存储任何实质的数据对象，其 next 域指向 线性表中 0 号元素所在的结点，头结点的引入可以使线性表运算中的一些边界条件更容易处理。

package com.wjy.Data_Structure.linearlist.listslinkimpl;
import com.wjy.Data_Structure.linearlist.common.DefaultStrategy;
import com.wjy.Data_Structure.linearlist.common.List;
import com.wjy.Data_Structure.linearlist.common.SLNode;
import com.wjy.Data_Structure.linearlist.common.Strategy;
import com.wjy.Data_Structure.linearlist.exception.OutOfBoundaryException;
//线性表的单链表实现
public class ListSLinked implements List {
  private Strategy strategy; // 数据元素比较策略
  private SLNode head; // 单链表首结点引用
  private int size;// 线性表中数据元素的个数
  public ListSLinked() {
    this(new DefaultStrategy());
  }
  public ListSLinked(Strategy strategy) {
    this.strategy = strategy;
    head = new SLNode();
    size = 0;
  }
  /**
   * 辅助方法： 获取数据元素 e 所在结点的前驱结点
   *
   * @param e
   * @return
   */
  private SLNode getPreNode(Object e) {
    SLNode p = head;
    while (p.getNext() != null)
      if (strategy.equal(p.getNext().getData(), e))
        return p;
      else
        p = p.getNext();
    return null;
  }
  /**
   * 辅助方法： 获取序号为 0<=i<size 的元素所在结点的前驱结点
   *
   * @param i
   * @return
   */
  private SLNode getPreNode(int i) {
    SLNode p = head;
    for (; i > 0; i--)
      p = p.getNext();
    return p;
  }
  /**
   * 辅助方法： 获取序号为 0<=i<size 的元素所在结点
   *
   * @param i
   * @return
   */
  private SLNode getNode(int i) {
    SLNode p = head.getNext();
    for (; i > 0; i--)
      p = p.getNext();
    return p;
  }
  @Override
  public int getSize() {
    return size;
  }
  @Override
  public boolean isEmpty() {
    return size == 0;
  }
  @Override
  public boolean contains(Object e) {
    return indexOf(e) != -1;
  }
  @Override
  public int indexOf(Object e) {
    SLNode p = head.getNext();
    int index = 0;
    while (p != null)
      if (strategy.equal(p.getData(), e)) {
        return index;
      } else {
        index++;
        p = p.getNext();
      }
    return -1;
  }
  @Override
  public void insert(int i, Object e) throws OutOfBoundaryException {
    if (i < 0 || i > size)
      throw new OutOfBoundaryException("错误，指定的插入序号越界");
    SLNode p = getPreNode(i);
    SLNode q = new SLNode(e, p.getNext());
    p.setNext(q);
    size++;
    return;
  }
  @Override
  public boolean insertBefore(Object obj, Object e) {
    SLNode p = getPreNode(obj);
    if (p != null) {
      SLNode q = new SLNode(e, p.getNext());
      p.setNext(q);
      size++;
      return true;
    }
    return false;
  }
  @Override
  public boolean insertAfter(Object obj, Object e) {
    SLNode p = head.getNext();
    while (p != null)
      if (strategy.equal(p.getData(), obj)) {
        SLNode q = new SLNode(e, p.getNext());
        p.setNext(q);
        size++;
        return true;
      } else {
        p = p.getNext();
      }
    return false;
  }
  @Override
  public Object remove(int i) throws OutOfBoundaryException {
    if (i < 0 || i >= size)
      throw new OutOfBoundaryException("错误，指定的删除序号越界。");
    SLNode p = getPreNode(i);
    Object obj = p.getNext().getData();
    p.setNext(p.getNext().getNext());
    size--;
    return obj;
  }
  @Override
  public boolean remove(Object e) {
    SLNode p = getPreNode(e);
    if (p != null) {
      p.setNext(p.getNext().getNext());
      size--;
      return true;
    }
    return false;
  }
  @Override
  public Object replace(int i, Object e) throws OutOfBoundaryException {
    if (i < 0 || i >= size)
      throw new OutOfBoundaryException("错误，指定的序号越界。");
    SLNode p = getNode(i);
    Object obj = p.getData();
    p.setData(e);
    return obj;
  }
  @Override
  public Object get(int i) throws OutOfBoundaryException {
    if (i < 0 || i >= size)
      throw new OutOfBoundaryException("错误，指定的序号越界。");
    SLNode p = getNode(i);
    return p.getData();
  }
}

简单的测试用例

package com.wjy.Data_Structure.linearlist.listslinkimpl;
import org.junit.Test;
import com.wjy.Data_Structure.linearlist.listslinkimpl.ListSLinked;
public class ListSLinkedTest {
  @Test
  public void testInsert() {
    ListSLinked list = new ListSLinked();
    for (int i = 0; i < 10; i++) {
      list.insert(i, i + 1);
    }
    System.out.println("删除：" + list.remove(0));
    System.out.println(list.contains(1));
    list.insertBefore(2, 100);
    list.insertAfter(2, 101);
    list.replace(list.getSize() - 1, 1000);
    for (int i = 0; i < list.getSize(); i++) {
      System.out.println(list.get(i));
    }
  }
}

数据结构学习代码仓库：

https://git.oschina.net/wjyonlyone/DataStructure

以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，同时也希望多多支持！

# Java  # 数据结构  # java实现线性表及其算法  # java 线性表接口的实例详解  # java线性表的存储结构及其代码实现  # Java数据结构之线性表  # java线性表排序示例分享  # Java实现线性表的链式存储  # 链表  # 线性表  # 链式  # 多个  # 而在  # 种方法  # 更容易  # 中不  # 即用  # 增加了  # 有两个  # 这种方法  # 在每个  # implements  # SLNode  # element  # private  # obj  # param 

相关文章： 公司门户网站制作流程,华为官网怎么做？  免费制作海报的网站,哪位做平面的朋友告诉我用什么软件做海报比较好?ps还是cd还是ai这几个软件我都会些我是做网页的？  c# F# 的 MailboxProcessor 和 C# 的 Actor 模型  如何快速搭建响应式可视化网站？  建站之星logo尺寸如何设置最合适？  如何撰写建站申请书？关键要点有哪些？  如何快速上传建站程序避免常见错误？  非常酷的网站设计制作软件,酷培ai教育官方网站？  西安大型网站制作公司,西安招聘网站最好的是哪个？  齐河建站公司：营销型网站建设与SEO优化双核驱动策略  建站之星如何配置系统实现高效建站？  制作网站的软件免费下载,免费制作app哪个平台好？  全景视频制作网站有哪些,全景图怎么做成网页？  如何通过建站之星自助学习解决操作问题？  宝华建站服务条款解析：五站合一功能与SEO优化设置指南  如何通过VPS搭建网站快速盈利？  如何选择域名并搭建高效网站？  如何通过网站建站时间优化SEO与用户体验？  网站插件制作软件免费下载,网页视频怎么下到本地插件？  猪八戒网站制作视频,开发一个猪八戒网站，大约需要多少？或者自己请程序员，需要什么程序员，多少程序员能完成？  小视频制作网站有哪些,有什么看国内小视频的网站，求推荐？  建站之星CMS五站合一模板配置与SEO优化指南  Python如何创建带属性的XML节点  如何用搬瓦工VPS快速搭建个人网站？  上海网站制作网页,上海本地的生活网站有哪些？最好包括生活的各个方面的？  如何选择高效便捷的WAP商城建站系统？  如何通过多用户协作模板快速搭建高效企业网站？  python的本地网站制作,如何创建本地站点？  建站之星会员如何解锁更多建站功能？  如何挑选高效建站主机与优质域名？  利用JavaScript实现拖拽改变元素大小  表情包在线制作网站免费,表情包怎么弄？  临沂网站制作公司有哪些,临沂第四中学官网？  如何在IIS7上新建站点并设置安全权限？  如何彻底卸载建站之星软件？  高端网站建设与定制开发一站式解决方案 中企动力  建站之星展会模板：智能建站与自助搭建高效解决方案  网站网页制作电话怎么打,怎样安装和使用钉钉软件免费打电话？  公司网站制作需要多少钱,找人做公司网站需要多少钱？  c++怎么编写动态链接库dll_c++ __declspec(dllexport)导出与调用【方法】  如何高效配置香港服务器实现快速建站？  mc皮肤壁纸制作器,苹果平板怎么设置自己想要的壁纸我的世界？  建站VPS能否同时实现高效与安全翻墙？  c++ stringstream用法详解_c++字符串与数字转换利器  外汇网站制作流程,如何在工商银行网站上做外汇买卖？  长沙做网站要多少钱,长沙国安网络怎么样？  香港服务器租用费用高吗？如何避免常见误区？  如何用西部建站助手快速创建专业网站？  如何通过可视化优化提升建站效果？  如何高效配置IIS服务器搭建网站？