今天就跟大家聊聊有關(guān)java中線性表的存儲(chǔ)結(jié)構(gòu)是什么，可能很多人都不太了解，為了讓大家更加了解，小編給大家總結(jié)了以下內(nèi)容，希望大家根據(jù)這篇文章可以有所收獲。
成都創(chuàng)新互聯(lián)公司專注于成都網(wǎng)站制作、網(wǎng)站建設(shè)、網(wǎng)頁設(shè)計(jì)、網(wǎng)站制作、網(wǎng)站開發(fā)。公司秉持“客戶至上,用心服務(wù)”的宗旨,從客戶的利益和觀點(diǎn)出發(fā),讓客戶在網(wǎng)絡(luò)營銷中找到自己的駐足之地。尊重和關(guān)懷每一位客戶，用嚴(yán)謹(jǐn)?shù)膽B(tài)度對待客戶，用專業(yè)的服務(wù)創(chuàng)造價(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è)對一個(gè)的關(guān)系
樹形結(jié)構(gòu)：數(shù)據(jù)元素之間存在一個(gè)對多個(gè)關(guān)系
圖形結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)：數(shù)據(jù)元素之間存在多個(gè)對多個(gè)的關(guān)系
對于數(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{ private int DEFAULT_SIZE = 16; //保存數(shù)組的長度。 private int capacity; //定義一個(gè)數(shù)組用于保存順序線性表的元素 private Object[] elementData; //保存順序表中元素的當(dāng)前個(gè)數(shù) private int size = 0; //以默認(rèn)數(shù)組長度創(chuàng)建空順序線性表 public SequenceList() { capacity = DEFAULT_SIZE; elementData = new Object[capacity]; } //以一個(gè)初始化元素來創(chuàng)建順序線性表 public SequenceList(T element) { this(); elementData[0] = element; size++; } /** * 以指定長度的數(shù)組來創(chuàng)建順序線性表 * @param element 指定順序線性表中第一個(gè)元素 * @param initSize 指定順序線性表底層數(shù)組的長度 */ 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ù)組的原有長度小于目前所需的長度 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{ //定義一個(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++; } //返回鏈表的長度 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è)長度固定的數(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í)性能要好
看完上述內(nèi)容，你們對java中線性表的存儲(chǔ)結(jié)構(gòu)是什么有進(jìn)一步的了解嗎？如果還想了解更多知識(shí)或者相關(guān)內(nèi)容，請關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，感謝大家的支持。
重慶分公司
重慶分公司
