快捷導(dǎo)航

java線性表的存儲(chǔ)結(jié)構(gòu)及其代碼實(shí)現(xiàn)

更新時(shí)間：2020年10月29日 13:12:47 作者：Angel_Kitty

這篇文章主要為大家詳細(xì)介紹了Java數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)筆記第一篇，線性表的存儲(chǔ)結(jié)構(gòu)及其代碼實(shí)現(xiàn)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下

Java數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)筆記第一篇：

用程序后在那個(gè)的數(shù)據(jù)大致有四種基本的邏輯結(jié)構(gòu)：

集合：數(shù)據(jù)元素之間只有"同屬于一個(gè)集合"的關(guān)系
線性結(jié)構(gòu)：數(shù)據(jù)元素之間存在一個(gè)對(duì)一個(gè)的關(guān)系
樹形結(jié)構(gòu)：數(shù)據(jù)元素之間存在一個(gè)對(duì)多個(gè)關(guān)系
圖形結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)：數(shù)據(jù)元素之間存在多個(gè)對(duì)多個(gè)的關(guān)系

對(duì)于數(shù)據(jù)不同的邏輯結(jié)構(gòu)，計(jì)算機(jī)在物理磁盤上通常有兩種屋里存儲(chǔ)結(jié)構(gòu)

順序存儲(chǔ)結(jié)構(gòu)
鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

本篇博文主要講的是線性結(jié)構(gòu)，而線性結(jié)構(gòu)主要是線性表，非線性結(jié)構(gòu)主要是樹和圖。

線性表的基本特征：

總存在唯一的第一個(gè)數(shù)據(jù)元素
總存在唯一的最后一個(gè)數(shù)據(jù)元素
除第一個(gè)數(shù)據(jù)元素外，集合中的每一個(gè)數(shù)據(jù)元素都只有一個(gè)前驅(qū)的數(shù)據(jù)元素
除最后一個(gè)數(shù)據(jù)元素外，集合中的每一個(gè)數(shù)據(jù)元素都只有一個(gè)后繼的數(shù)據(jù)元素

1.線性表的順序存儲(chǔ)結(jié)構(gòu)：是指用一組地址連續(xù)的存儲(chǔ)單元一次存放線性表的元素。為了使用順序結(jié)構(gòu)實(shí)現(xiàn)線性表，程序通常會(huì)采用數(shù)組來保存線性中的元素，是一種隨機(jī)存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)，適合隨機(jī)訪問。java中ArrayList類是線性表的數(shù)組實(shí)現(xiàn)。

import java.util.Arrays;
public class SequenceList<T>
{
 private int DEFAULT_SIZE = 16;
 //保存數(shù)組的長(zhǎng)度。
 private int capacity;
 //定義一個(gè)數(shù)組用于保存順序線性表的元素
 private Object[] elementData;
 //保存順序表中元素的當(dāng)前個(gè)數(shù)
 private int size = 0;
 //以默認(rèn)數(shù)組長(zhǎng)度創(chuàng)建空順序線性表
 public SequenceList()
 {
  capacity = DEFAULT_SIZE;
  elementData = new Object[capacity];
 }
 //以一個(gè)初始化元素來創(chuàng)建順序線性表
 public SequenceList(T element)
 {
  this();
  elementData[0] = element;
  size++;
 }
 /**
  * 以指定長(zhǎng)度的數(shù)組來創(chuàng)建順序線性表
  * @param element 指定順序線性表中第一個(gè)元素
  * @param initSize 指定順序線性表底層數(shù)組的長(zhǎng)度
  */
 public SequenceList(T element , int initSize)
 {
  capacity = 1;
  //把capacity設(shè)為大于initSize的最小的2的n次方
  while (capacity < initSize)
  {
   capacity <<= 1;
  }
  elementData = new Object[capacity];
  elementData[0] = element;
  size++;
 }
 //獲取順序線性表的大小
 public int length()
 {
  return size;
 }
 //獲取順序線性表中索引為i處的元素
 public T get(int i)
 {
  if (i < 0 || i > size - 1)
  {
   throw new IndexOutOfBoundsException("線性表索引越界");
  }
  return (T)elementData[i];
 }
 //查找順序線性表中指定元素的索引
 public int locate(T element)
 {
  for (int i = 0 ; i < size ; i++)
  {
   if (elementData[i].equals(element))
   {
    return i;
   }
  }
  return -1;
 }
 //向順序線性表的指定位置插入一個(gè)元素。
 public void insert(T element , int index)
 {
  if (index < 0 || index > size)
  {
   throw new IndexOutOfBoundsException("線性表索引越界");
  }
  ensureCapacity(size + 1);
  //將index處以后所有元素向后移動(dòng)一格。
  System.arraycopy(elementData , index , elementData
    , index + 1 , size - index);
  elementData[index] = element;
  size++;
 }
 //在線性順序表的開始處添加一個(gè)元素。
 public void add(T element)
 {
  insert(element , size);
 }
 //很麻煩，而且性能很差
 private void ensureCapacity(int minCapacity)
 {
  //如果數(shù)組的原有長(zhǎng)度小于目前所需的長(zhǎng)度
  if (minCapacity > capacity)
  {
   //不斷地將capacity * 2，直到capacity大于minCapacity為止
   while (capacity < minCapacity)
   {
    capacity <<= 1;
   }
   elementData = Arrays.copyOf(elementData , capacity);
  }
 }
 //刪除順序線性表中指定索引處的元素
 public T delete(int index)
 {
  if (index < 0 || index > size - 1)
  {
   throw new IndexOutOfBoundsException("線性表索引越界");
  }
  T oldValue = (T)elementData[index];
  int numMoved = size - index - 1;
  if (numMoved > 0)
  {
   System.arraycopy(elementData , index+1
    , elementData, index ,  numMoved);
  }
  //清空最后一個(gè)元素
  elementData[--size] = null; 
  return oldValue;
 }
 //刪除順序線性表中最后一個(gè)元素
 public T remove()
 {
  return delete(size - 1);
 }
 //判斷順序線性表是否為空表
 public boolean empty()
 {
  return size == 0;
 }
 //清空線性表
 public void clear()
 {
  //將底層數(shù)組所有元素賦為null
  Arrays.fill(elementData , null);
  size = 0;
 }
 public String toString()
 {
  if (size == 0)
  {
   return "[]";
  }
  else
  {
   StringBuilder sb = new StringBuilder("[");
   for (int i = 0 ; i < size ; i++ )
   {
    sb.append(elementData[i].toString() + ", ");
   }
   int len = sb.length();
   return sb.delete(len - 2 , len).append("]").toString();
  }
 }
}

2.線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu):將采用一組地址的任意的存儲(chǔ)單元存放線性表中的數(shù)據(jù)元素。
鏈表又可分為：

單鏈表：每個(gè)節(jié)點(diǎn)只保留一個(gè)引用，該引用指向當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，沒有引用指向頭結(jié)點(diǎn)，尾節(jié)點(diǎn)的next引用為null。
循環(huán)鏈表：一種首尾相連的鏈表。
雙向鏈表：每個(gè)節(jié)點(diǎn)有兩個(gè)引用，一個(gè)指向當(dāng)前節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)，另外一個(gè)指向當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)。

下面給出線性表雙向鏈表的實(shí)現(xiàn)：java中LinkedList是線性表的鏈?zhǔn)綄?shí)現(xiàn)，是一個(gè)雙向鏈表。

public class DuLinkList<T>
{
 //定義一個(gè)內(nèi)部類Node，Node實(shí)例代表鏈表的節(jié)點(diǎn)。
 private class Node
 {
  //保存節(jié)點(diǎn)的數(shù)據(jù)
  private T data;
  //指向上個(gè)節(jié)點(diǎn)的引用
  private Node prev;
  //指向下個(gè)節(jié)點(diǎn)的引用
  private Node next;
  //無參數(shù)的構(gòu)造器
  public Node()
  {
  }
  //初始化全部屬性的構(gòu)造器
  public Node(T data , Node prev , Node next)
  {
   this.data = data;
   this.prev = prev;
   this.next = next;
  }
 }
 //保存該鏈表的頭節(jié)點(diǎn)
 private Node header;
 //保存該鏈表的尾節(jié)點(diǎn)
 private Node tail;
 //保存該鏈表中已包含的節(jié)點(diǎn)數(shù)
 private int size;
 //創(chuàng)建空鏈表
 public DuLinkList()
 {
  //空鏈表，header和tail都是null
  header = null;
  tail = null;
 }
 //以指定數(shù)據(jù)元素來創(chuàng)建鏈表，該鏈表只有一個(gè)元素
 public DuLinkList(T element)
 {
  header = new Node(element , null , null);
  //只有一個(gè)節(jié)點(diǎn)，header、tail都指向該節(jié)點(diǎn)
  tail = header;
  size++;
 }
 //返回鏈表的長(zhǎng)度 
 public int length()
 {
  return size;
 }

 //獲取鏈?zhǔn)骄€性表中索引為index處的元素
 public T get(int index)
 {
  return getNodeByIndex(index).data;
 }
 //根據(jù)索引index獲取指定位置的節(jié)點(diǎn)
 private Node getNodeByIndex(int index)
 {
  if (index < 0 || index > size - 1)
  {
   throw new IndexOutOfBoundsException("線性表索引越界");
  }
  if (index <= size / 2)
  {
   //從header節(jié)點(diǎn)開始
   Node current = header;
   for (int i = 0 ; i <= size / 2 && current != null
    ; i++ , current = current.next)
   {
    if (i == index)
    {
     return current;
    }
   }
  }
  else
  {
   //從tail節(jié)點(diǎn)開始搜索
   Node current = tail;
   for (int i = size - 1 ; i > size / 2 && current != null
    ; i++ , current = current.prev)
   {
    if (i == index)
    {
     return current;
    }
   }
  }
  return null;
 }
 //查找鏈?zhǔn)骄€性表中指定元素的索引
 public int locate(T element)
 {
  //從頭節(jié)點(diǎn)開始搜索
  Node current = header;
  for (int i = 0 ; i < size && current != null
   ; i++ , current = current.next)
  {
   if (current.data.equals(element))
   {
    return i;
   }
  }
  return -1;
 }
 //向線性鏈?zhǔn)奖淼闹付ㄎ恢貌迦胍粋€(gè)元素。
 public void insert(T element , int index)
 {
  if (index < 0 || index > size)
  {
   throw new IndexOutOfBoundsException("線性表索引越界");
  }
  //如果還是空鏈表
  if (header == null)
  {
   add(element);
  }
  else
  {
   //當(dāng)index為0時(shí)，也就是在鏈表頭處插入
   if (index == 0)
   {
    addAtHeader(element);
   }
   else
   {
    //獲取插入點(diǎn)的前一個(gè)節(jié)點(diǎn)
    Node prev = getNodeByIndex(index - 1);
    //獲取插入點(diǎn)的節(jié)點(diǎn)
    Node next = prev.next;
    //讓新節(jié)點(diǎn)的next引用指向next節(jié)點(diǎn)，prev引用指向prev節(jié)點(diǎn)
    Node newNode = new Node(element , prev , next);
    //讓prev的next指向新節(jié)點(diǎn)。
    prev.next = newNode;
    //讓prev的下一個(gè)節(jié)點(diǎn)的prev指向新節(jié)點(diǎn)
    next.prev = newNode;
    size++;
   }
  }
 }
 //采用尾插法為鏈表添加新節(jié)點(diǎn)。
 public void add(T element)
 {
  //如果該鏈表還是空鏈表
  if (header == null)
  {
   header = new Node(element , null , null);
   //只有一個(gè)節(jié)點(diǎn)，header、tail都指向該節(jié)點(diǎn)
   tail = header;
  }
  else
  {
   //創(chuàng)建新節(jié)點(diǎn),新節(jié)點(diǎn)的pre指向原tail節(jié)點(diǎn)
   Node newNode = new Node(element , tail , null);
   //讓尾節(jié)點(diǎn)的next指向新增的節(jié)點(diǎn)
   tail.next = newNode;
   //以新節(jié)點(diǎn)作為新的尾節(jié)點(diǎn)
   tail = newNode;
  }
  size++;
 }
 //采用頭插法為鏈表添加新節(jié)點(diǎn)。
 public void addAtHeader(T element)
 {
  //創(chuàng)建新節(jié)點(diǎn)，讓新節(jié)點(diǎn)的next指向原來的header
  //并以新節(jié)點(diǎn)作為新的header
  header = new Node(element , null , header);
  //如果插入之前是空鏈表
  if (tail == null)
  {
   tail = header;
  }
  size++;
 }
 //刪除鏈?zhǔn)骄€性表中指定索引處的元素
 public T delete(int index)
 {
  if (index < 0 || index > size - 1)
  {
   throw new IndexOutOfBoundsException("線性表索引越界");
  }
  Node del = null;
  //如果被刪除的是header節(jié)點(diǎn)
  if (index == 0)
  {
   del = header;
   header = header.next;
   //釋放新的header節(jié)點(diǎn)的prev引用
   header.prev = null;
  }
  else
  {
   //獲取刪除點(diǎn)的前一個(gè)節(jié)點(diǎn)
   Node prev = getNodeByIndex(index - 1);
   //獲取將要被刪除的節(jié)點(diǎn)
   del = prev.next;
   //讓被刪除節(jié)點(diǎn)的next指向被刪除節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)。
   prev.next = del.next;
   //讓被刪除節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)的prev指向prev節(jié)點(diǎn)。
   if (del.next != null)
   {
    del.next.prev = prev;
   }  
   //將被刪除節(jié)點(diǎn)的prev、next引用賦為null.
   del.prev = null;
   del.next = null;
  }
  size--;
  return del.data;
 }
 //刪除鏈?zhǔn)骄€性表中最后一個(gè)元素
 public T remove()
 {
  return delete(size - 1);
 }
 //判斷鏈?zhǔn)骄€性表是否為空鏈表
 public boolean empty()
 {
  return size == 0;
 }
 //清空線性表
 public void clear()
 {
  //將底層數(shù)組所有元素賦為null
  header = null;
  tail = null;
  size = 0;
 }
 public String toString()
 {
  //鏈表為空鏈表時(shí)
  if (empty())
  {
   return "[]";
  }
  else
  {
   StringBuilder sb = new StringBuilder("[");
   for (Node current = header ; current != null
    ; current = current.next )
   {
    sb.append(current.data.toString() + ", ");
   }
   int len = sb.length();
   return sb.delete(len - 2 , len).append("]").toString();
  }
 }
 public String reverseToString()
 {
  //鏈表為空鏈表時(shí)
  if (empty())
  {
   return "[]";
  }
  else
  {
   StringBuilder sb = new StringBuilder("[");
   for (Node current = tail ; current != null 
    ; current = current.prev )
   {
    sb.append(current.data.toString() + ", ");
   }
   int len = sb.length();
   return sb.delete(len - 2 , len).append("]").toString();
  }
 }
}

線性表的兩種實(shí)現(xiàn)比較

空間性能：

順序表：順序表的存儲(chǔ)空間是靜態(tài)分布的，需要一個(gè)長(zhǎng)度固定的數(shù)組，因此總有部分?jǐn)?shù)組元素被浪費(fèi)。

鏈表：鏈表的存儲(chǔ)空間是動(dòng)態(tài)分布的，因此不會(huì)空間浪費(fèi)。但是由于鏈表需要而外的空間來為每個(gè)節(jié)點(diǎn)保存指針，因此要犧牲一部分空間。

時(shí)間性能：

順序表：順序表中元素的邏輯順序與物理存儲(chǔ)順序是保持一致的，而且支持隨機(jī)存取。因此順序表在查找、讀取時(shí)性能很好。

鏈表：鏈表采用鏈?zhǔn)浇Y(jié)構(gòu)來保存表內(nèi)元素，因此在插入、刪除元素時(shí)性能要好

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

您可能感興趣的文章: