Java实现单向链表数据结构

本文章同步到本人的博客站点燕归来

链表是一种数据结构，和数组同级。比如，Java中我们使用的ArrayList，其实现原理是数组。而LinkedList的实现原理就是链表了。链表在进行循环遍历时效率不高，但是插入和删除时优势明显。下面对单向链表做一个介绍。

什么是单向链表?

单向链表是一种线性表，实际上是由节点（Node）组成的，一个链表拥有不定数量的节点。其数据在内存中存储是不连续的，它存储的数据分散在内存中，每个结点只能也只有它能知道下一个结点的存储位置。由N各节点（Node）组成单向链表，每一个Node记录本Node的数据及下一个Node。向外暴露的只有一个头节点（Head），我们对链表的所有操作，都是直接或者间接地通过其头节点来进行的。

image

单向链表的代码实现

链表的过程这里不做过多的赘述，下面我们看一下使用Java实现简单的单向链表:


package com.tao.struct.list;

/** @author 周涛 */
public class LinkList<T> {

  private Node head;

  private Node rear;

  private Node point;

  private int length;

    //内部私有类
  private class Node {

    private T object;

    private Node next;

    public Node() {
      object = null;
    }

    public Node(T object) {
      this.object = object;
    }

    public Node(T object, Node next) {
      this.object = object;
      this.next = next;
    }
  }

  public LinkList() {
    head = new Node();
    rear = head;
    length = 0;
  }

  public void add(T o) {
    point = new Node(o);
    rear.next = point;
    rear = point;
    length++;
  }

  /**
   * 在链表尾部新增数据
   *
   * @param index
   * @param o
   */
  public void add(int index, T o) {
    if (index > length) {
      throw new IllegalArgumentException();
    }
    // 移动Point到指定位置
    movePoint(index);
    Node tmp = new Node(o);

    tmp.next = point.next;
    point.next = tmp;
    length++;
  }

  /**
   * 将point指针移到index位置
   *
   * @param index
   */
  private void movePoint(int index) {
    point = head;
    while (point.next != null) {
      if (index == 0) {
        break;
      }
      index--;
      point = point.next;
    }
  }

  /** 删除链表所有数据 */
  public void clear() {
    head = null;
    length = 0;
    rear = head;
    System.gc();
  }

  /**
   * 获取指定位置的数据
   *
   * @param index
   * @return
   */
  public T get(int index) {
    movePoint(index);
    return point.next.object;
  }

  /**
   * 判断链表是不是空的
   *
   * @return
   */
  public boolean isEmpty() {
    return length == 0;
  }

  /**
   * 移除指定位置的数据
   *
   * @param index
   */
  public void remove(int index) {
    movePoint(index);
    point.next = point.next.next;
    length --;
  }

  /**
   * 获取链表的长度信息
   *
   * @return
   */
  public int size() {
    return length;
  }

  /**
   * 更新指定位置的数据
   *
   * @param index
   * @param o
   */
  public void set(int index, T o) {
    movePoint(index);
    point.next.object = o;
  }

  /** 遍历输出链表的数据 */
  public void traverse() {
    point = head;
    if (point != null) {
      while (point.next != null) {
        System.out.print(point.next.object + "\t");
        point = point.next;
      }
    }
    System.out.println();
  }
}

测试代码

注意，此测试依赖JUnit4单元测试框架

package com.tao.struct.list;

import junit.framework.TestCase;

/**
 * @author 周涛
 */
public class LinkListTest extends TestCase {

  public void testAdd() {
    LinkList<String> linkList=new LinkList<String>();
    //测试在尾部新增数据
    for(int i=0;i<10;i++){
      linkList.add(String.valueOf(i));
    }
    // 遍历输出链表
    System.out.print("数据信息为:");
    linkList.traverse();


    //测试在指定位置插入数据
    linkList.add(3,"*");
    System.out.print("插入新的数据后:");
    linkList.traverse();

    //获取指定位置的数据
    String s = linkList.get(3);
    System.out.println("获取第3位置的数据是:"+s);

    //移除指定位置的数据
    linkList.remove(3);
    System.out.print("移除第3位置的数据后:");
    linkList.traverse();

    //更新指定位置数据后
    linkList.set(3,"333");
    System.out.print("更新指定位置数据后");
    linkList.traverse();

    // 判断链表是不是空的
    System.out.println("当前链表长度:" + linkList.size());
    System.out.println("当前链表是否为空:" + linkList.isEmpty());
    linkList.clear();
    System.out.println("清空链表后是否为空:" + linkList.isEmpty());

  }

}

测试结果