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

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