java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言, 是由 Sun Microsystems 公司于 1995 年 5 月推出的 Java 程序设计语言和 Java 平台 (即 JavaEE(j2ee), JavaME(j2me), JavaSE(j2se)) 的总称
本文主要介绍了 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
来源: http://www.phperz.com/article/18/0220/358685.html