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

2019-11-26 13:10:58

字体：大中小

来源：转载

供稿：网友

线性表的链式存储与实现

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

单链表

链表是一系列的存储数据元素的单元通过指针串接起来形成的，因此每个单元至少有两个域，一个域用于数据元素的存储，另一个域是指向其他单元的指针。这里具有一个数据域和多个指针域的存储单元通常称为结点（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 三种将list转换为map的方法详解

下一篇：Spring集成Quartz的简单配置的方法