Java数据结构之简单链表的定义与实现方法示例

更新时间：2017年10月23日 11:04:16 作者：CharlinGod

这篇文章主要介绍了Java数据结构之简单链表的定义与实现方法,简单描述了链接的概念、原理,并结合实例形式分析了java定义与使用链表的相关步骤与操作技巧,需要的朋友可以参考下

本文实例讲述了Java数据结构之简单链表的定义与实现方法。链表实现链表实现分享给大家供大家参考，具体如下：

一、概述：

1、原理：

只有一个数据项（链接点Link)，每个数据插入时都是对第一个数据的引用。

2、插入数据说明：

链表是单向的，当前节点的位置保存在前驱节点的指针域，所以在插入的时候，要先将新节点的指针域指向当前节点（新节点插入在该节点之前），然后当前节点的前驱结点的指针域指向新节点。1.若插入节点在最前面，则head指向插入节点（即待插入节点变为头结点），插入节点的next指针指向原链表的第一个节点。initlist 初始化循环链表,开辟一个空间作为头结点,并让l l- next先让它指向自己,令链表循环起来. listinsert 向循环链表里面插入数据 包括编号和密码 , displist 以定义的头结点为第一个数,输出循环链表.josephus 主要用于解决约瑟夫环问题,首先调用initlist 建立循环链表,再调用listinsert 插入数据,再调用displist 把储存的数据输出来.定义两个指针s和q,再定义count作为计数器,此时需要任意输入一个正整数x作为初始报数上限值,当计数器count x时就把该指针所指向的数据输出并把该数据赋给x,作为新的报数上限值.然后删除该结点,s和q的主要作用是在把输出数据之后的结点删除.如此循环,直到还剩最后一个结点,同时定义a[i],b[i]用来储存编号和密码。

3、插入数据图：

4、特点：先进后出

5、实现功能：

数据插入，指定位置插入，显示，查询，删除等

6、删除原理

7、插入头节点原理

二、实现：

1、创建节点

/**
 * @描述     节点
 * @项目名称   Java_DataStruct
 * @包名     com.struct.linklist
 * @类名     Node
 * @author   chenlin
 * @date    2010年6月26日 上午7:58:59
 * @version   1.0 
 */
public class Node {
  public long data;
  public Node next;
  public long getData() {
    return data;
  }
  public void display(){
    System.out.print(data + " ");
  }
  public Node(long data) {
    this.data = data;
  }
  public void setData(long data) {
    this.data = data;
  }
  public Node getNext() {
    return next;
  }
  public void setNext(Node next) {
    this.next = next;
  }
}

2、链表实现

/**
 * @描述     链表
 * @项目名称   Java_DataStruct
 * @包名     com.struct.linklist
 * @类名     LinkList
 * @author   chenlin
 * @date    2010年6月26日 上午8:00:28
 * @version   1.0 
 */
public class LinkList {
  private Node first;
  public LinkList(){
    first = null;
  }
  /**
   * 插入数据
   * @param value
   */
  public void insertFirst(long value){
    Node newNode = new Node(value);
    if (first == null) {
      first = newNode;
    }else {
      //把first节点往下移动
      newNode.next = first;
      //把插入的节点作为新的节点
      first = newNode;
    }
  }
  /**
   * 删除头节点
   * @param value
   * @return
   */
  public Node deleteFirst(){
    if (first == null) {
      throw new RuntimeException("链表数据不存在");
    }
    Node temp = first;
    first = temp.next;
    return temp;
  }
  public Node deleteByKey(long key){
    Node current = first;
    Node last = first;
    while(current.data != key){
      if (current.next == null) {
        System.out.println("没找到节点");
        return null;
      }
      last = current;
      current = current.next;
    }
    if (current == first) {
      //return deleteFirst();
      //指向下个就表示删除第一个
      first = first.next;
    }else {
      last.next = current.next;
    }
    return current;
  }
  /**
   * 显示所有的数据
   */
  public void display(){
    if (first == null) {
      //throw new RuntimeException("链表数据不存在");
      return;
    }
    Node current = first;
    while(current != null){
      current.display();
      current = current.next;
    }
    System.out.println("---------------");
  }
  /**
   * 查找节点1
   * @param value
   * @return
   */
  public Node findByValue(long value){
    Node current = first;
    while(current != null){
      if (current.data != value) {
        current = current.next;
      }else {
        break;
      }
    }
    if (current == null) {
      System.out.println("没找到");
      return null;
    }
    return current;
  }
  /**
   * 查找节点2
   * 
   * @param key
   * @return
   */
  public Node findByKey(long key) {
    Node current = first;
    while (current.data != key) {
      if (current.next == null) {
        System.out.println("没找到");
        return null;
      }
      current = current.next;
    }
    return current;
  }
  /**
   * 根据索引查找对应的值
   * @param position
   * @return
   */
  public Node findByPosition(int position){
    Node current = first;
    //为什么是position - 1，因为要使用遍历，让current指向下一个， 所以position - 1的下个node就是要找的值
    for (int i = 0; i < position - 1 ; i++) {
      current = current.next;
    }
    return current;
  }
  public static void main(String[] args) {
    LinkList linkList = new LinkList();
    linkList.insertFirst(21);
    linkList.insertFirst(22);
    linkList.insertFirst(23);
    linkList.insertFirst(24);
    linkList.insertFirst(25);
    linkList.insertFirst(26);
    linkList.insertFirst(27);
    System.out.println("脚本之家测试结果：");
    linkList.display();
    System.out.println("---查找-------------------------------------");
    linkList.findByKey(25).display();
    System.out.println("--删除first-------------------------------------");
    //linkList.deleteFirst().display();
    ///linkList.deleteFirst().display();
    //linkList.deleteFirst().display();
    //linkList.deleteFirst().display();
    System.out.println("-删除指定值---------------------------------------");
    linkList.deleteByKey(27).display();
    linkList.deleteByKey(21).display();
    System.out.println("----------------------------------------");
    linkList.display();
  }
}

显示结果：

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-99126-1.html