用Java實現(xiàn)一個靜態(tài)鏈表的方法步驟

更新時間：2020年02月11日 09:38:21 作者：孫華棟

這篇文章主要介紹了用Java實現(xiàn)一個靜態(tài)鏈表的方法步驟，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

什么是靜態(tài)鏈表？

對于線性鏈表，也可用一維數(shù)組來進行描述。這種描述方法便于在沒有指針類型的高級程序設(shè)計語言中使用鏈表結(jié)構(gòu)。

用數(shù)組描述的鏈表，即稱為靜態(tài)鏈表。

在C語言中，靜態(tài)鏈表的表現(xiàn)形式即為結(jié)構(gòu)體數(shù)組，結(jié)構(gòu)體變量包括數(shù)據(jù)域data和游標(biāo)CUR。

靜態(tài)鏈表的節(jié)點

數(shù)據(jù)域：用于存儲數(shù)據(jù)元素的值
游標(biāo)：即數(shù)組下標(biāo)，表示直接后繼元素所在數(shù)組中的位置

public class StaticLinkedListNode<T> { 
  public T data; // 數(shù)據(jù)
  public int cursor; // 游標(biāo)
  ...
}

注：通常靜態(tài)鏈表會將第一個數(shù)據(jù)元素放到數(shù)組下標(biāo)為1(即a[1])的位置中。

備用鏈表

靜態(tài)鏈表中，除了數(shù)據(jù)本身通過游標(biāo)組成鏈表外，還需要有一條連接各個空閑位置的鏈表，稱為備用鏈表。

作用：回收數(shù)組中未使用或者之前使用過(現(xiàn)在不用)的存儲空間，留待后期使用。即靜態(tài)鏈表使用數(shù)組申請的物理空間中，存在兩個鏈表，一條連接數(shù)據(jù)，另一條連接數(shù)組中為使用的空間。

注：通常備用鏈表的表頭位于數(shù)組下標(biāo)為0(a[0])的位置,而數(shù)據(jù)鏈表的表頭位于數(shù)組下標(biāo)為1(a[1])的位置。

靜態(tài)鏈表中設(shè)置備用鏈表的好處是，可以清楚地知道數(shù)組中是否有空閑位置，以便數(shù)據(jù)鏈表添加新數(shù)據(jù)時使用。比如，若靜態(tài)鏈表中數(shù)組下標(biāo)為 0 的位置上存有數(shù)據(jù)，則證明數(shù)組已滿。

完整代碼

public class StaticLinkedListNode<T> {
  public T data;
  private int cursor;

  public StaticLinkedListNode(T data, int cursor) {
    this.cursor = cursor;
  }

  public T getData() {
    return data;
  }

  public void setData(T data) {
    this.data = data;
  }

  public int getCursor() {
    return cursor;
  }

  public void setCursor(int cursor) {
    this.cursor = cursor;
  }
}

public class StaticLinkedList<T> {
  StaticLinkedListNode[] nodes;
  private static final int MAX_SIZE = 100;
  private int length;

  public StaticLinkedList() {
    nodes = new StaticLinkedListNode[MAX_SIZE];
    for (int i = 0; i < MAX_SIZE; i++) {
      nodes[i] = new StaticLinkedListNode<T>(null, i + 1);
    }
    nodes[MAX_SIZE - 1].setCursor(0);
    this.length = 0;
  }

  // 鏈表實際長度
  public int Length() {
    return length;
  }

  // 判斷使用數(shù)組是否為空
  public boolean isEmpty() {
    return length == 0;
  }

  // 判斷備用鏈表是否為空
  public boolean isFull() {
    return length == MAX_SIZE;
  }

  // 插入一個節(jié)點
  public boolean addTo(T data, int index) {
    if (isFull() || index > MAX_SIZE || index < -1 || data == null)
      return false;
    if (index == 0) {
      insert(data);
      return true;
    }
    if (index > Length()) {
      index = Length();
    }
    // 獲取第一個使用節(jié)點的下標(biāo)
    int firstUse = nodes[MAX_SIZE - 1].getCursor();
    // 獲取備用數(shù)組第一個節(jié)點的下標(biāo)
    int firstNull = nodes[0].getCursor();
    for (int i = 1; i < index; i++) {
      firstUse = nodes[firstUse].getCursor();
    }
    // 獲取目標(biāo)節(jié)點的后續(xù)節(jié)點
    int nextUse = nodes[firstUse].getCursor();
    int nextNull = nodes[firstNull].getCursor();
    nodes[0].setCursor(nextNull);
    nodes[firstUse].setCursor(firstNull);
    nodes[firstNull].setCursor(nextUse);
    nodes[firstNull].setData(data);
    length++;
    return true;
  }

  public void insert(T data) {
    int t = nodes[MAX_SIZE - 1].getCursor();
    int firstNull = nodes[0].getCursor();
    nodes[MAX_SIZE - 1].setCursor(firstNull);
    nodes[0].setCursor(nodes[firstNull].getCursor());
    nodes[firstNull].setCursor(t);
    nodes[firstNull].setData(data);
    length++;
  }

  public void print() {
    int first = nodes[MAX_SIZE - 1].getCursor();
    System.out.println("鏈表：");
    for (int i = first; i != 0; ) {
      System.out.print(nodes[i].getData() + " ");
      i = nodes[i].getCursor();
    }
  }

  // 刪除指定節(jié)點
  public boolean delete(T data) {
    if (isEmpty()) {
      return false;
    }
    int temp = MAX_SIZE - 1;
    while (temp != 0) {
      if (nodes[nodes[temp].getCursor()].getData() == data) {
        int p = nodes[temp].getCursor();
        nodes[temp].setCursor(nodes[p].getCursor());
        nodes[p].setCursor(nodes[0].getCursor());
        nodes[0].setCursor(p);
        nodes[p].setData(null);
        length--;
        return true;
      }
      temp = nodes[temp].getCursor();
    }
    return false;
  }

  // 刪除所有節(jié)點
  public boolean deleteAll() {
    if (isEmpty()) {
      return true;
    }
    for (int i = 0; i < MAX_SIZE - 1; i++) {
      nodes[i].setCursor(i + 1);
      nodes[i].setData(null);
    }
    nodes[MAX_SIZE - 1].setCursor(0);
    nodes[MAX_SIZE - 1].setData(null);
    length = 0;
    return true;
  }

  public void printAll() {
    System.out.println("鏈表：");
    for (int i = 0; i < MAX_SIZE; i++) {
      System.out.print("[" + i + " " + nodes[i].getData() + " " + nodes[i].getCursor() + "]");
      if (i % 5 == 0 && i != 0) {
        System.out.println();
      }
    }
  }

  public static void main(String[] args) {
    StaticLinkedList<String> list = new StaticLinkedList<String>();
    list.insert("A");
    list.insert("B");
    list.insert("C");
    list.insert("D");
    list.insert("E");
    list.addTo("X", 2);
    System.out.println(list.Length());
    list.print();
//    list.printAll();
//    list.deleteAll();
  }
}

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: