java線性表的存儲結(jié)構(gòu)及其代碼實(shí)現(xiàn)
Java數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)筆記第一篇:
用程序后在那個的數(shù)據(jù)大致有四種基本的邏輯結(jié)構(gòu):
集合:數(shù)據(jù)元素之間只有"同屬于一個集合"的關(guān)系
線性結(jié)構(gòu):數(shù)據(jù)元素之間存在一個對一個的關(guān)系
樹形結(jié)構(gòu):數(shù)據(jù)元素之間存在一個對多個關(guān)系
圖形結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu):數(shù)據(jù)元素之間存在多個對多個的關(guān)系
對于數(shù)據(jù)不同的邏輯結(jié)構(gòu),計(jì)算機(jī)在物理磁盤上通常有兩種屋里存儲結(jié)構(gòu)
順序存儲結(jié)構(gòu)
鏈?zhǔn)酱鎯Y(jié)構(gòu)
本篇博文主要講的是線性結(jié)構(gòu),而線性結(jié)構(gòu)主要是線性表,非線性結(jié)構(gòu)主要是樹和圖。
線性表的基本特征:
總存在唯一的第一個數(shù)據(jù)元素
總存在唯一的最后一個數(shù)據(jù)元素
除第一個數(shù)據(jù)元素外,集合中的每一個數(shù)據(jù)元素都只有一個前驅(qū)的數(shù)據(jù)元素
除最后一個數(shù)據(jù)元素外,集合中的每一個數(shù)據(jù)元素都只有一個后繼的數(shù)據(jù)元素
1.線性表的順序存儲結(jié)構(gòu):是指用一組地址連續(xù)的存儲單元一次存放線性表的元素。為了使用順序結(jié)構(gòu)實(shí)現(xiàn)線性表,程序通常會采用數(shù)組來保存線性中的元素,是一種隨機(jī)存儲的數(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ù)組的長度。 private int capacity; //定義一個數(shù)組用于保存順序線性表的元素 private Object[] elementData; //保存順序表中元素的當(dāng)前個數(shù) private int size = 0; //以默認(rèn)數(shù)組長度創(chuàng)建空順序線性表 public SequenceList() { capacity = DEFAULT_SIZE; elementData = new Object[capacity]; } //以一個初始化元素來創(chuàng)建順序線性表 public SequenceList(T element) { this(); elementData[0] = element; size++; } /** * 以指定長度的數(shù)組來創(chuàng)建順序線性表 * @param element 指定順序線性表中第一個元素 * @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; } //向順序線性表的指定位置插入一個元素。 public void insert(T element , int index) { if (index < 0 || index > size) { throw new IndexOutOfBoundsException("線性表索引越界"); } ensureCapacity(size + 1); //將index處以后所有元素向后移動一格。 System.arraycopy(elementData , index , elementData , index + 1 , size - index); elementData[index] = element; size++; } //在線性順序表的開始處添加一個元素。 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); } //清空最后一個元素 elementData[--size] = null; return oldValue; } //刪除順序線性表中最后一個元素 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)酱鎯Y(jié)構(gòu):將采用一組地址的任意的存儲單元存放線性表中的數(shù)據(jù)元素。
鏈表又可分為:
單鏈表:每個節(jié)點(diǎn)只保留一個引用,該引用指向當(dāng)前節(jié)點(diǎn)的下一個節(jié)點(diǎn),沒有引用指向頭結(jié)點(diǎn),尾節(jié)點(diǎn)的next引用為null。
循環(huán)鏈表:一種首尾相連的鏈表。
雙向鏈表:每個節(jié)點(diǎn)有兩個引用,一個指向當(dāng)前節(jié)點(diǎn)的上一個節(jié)點(diǎn),另外一個指向當(dāng)前節(jié)點(diǎn)的下一個節(jié)點(diǎn)。
下面給出線性表雙向鏈表的實(shí)現(xiàn):java中LinkedList是線性表的鏈?zhǔn)綄?shí)現(xiàn),是一個雙向鏈表。
public class DuLinkList<T> { //定義一個內(nèi)部類Node,Node實(shí)例代表鏈表的節(jié)點(diǎn)。 private class Node { //保存節(jié)點(diǎn)的數(shù)據(jù) private T data; //指向上個節(jié)點(diǎn)的引用 private Node prev; //指向下個節(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)建鏈表,該鏈表只有一個元素 public DuLinkList(T element) { header = new Node(element , null , null); //只有一個節(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)奖淼闹付ㄎ恢貌迦胍粋€元素。 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時,也就是在鏈表頭處插入 if (index == 0) { addAtHeader(element); } else { //獲取插入點(diǎn)的前一個節(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的下一個節(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); //只有一個節(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)的前一個節(jié)點(diǎn) Node prev = getNodeByIndex(index - 1); //獲取將要被刪除的節(jié)點(diǎn) del = prev.next; //讓被刪除節(jié)點(diǎn)的next指向被刪除節(jié)點(diǎn)的下一個節(jié)點(diǎn)。 prev.next = del.next; //讓被刪除節(jié)點(diǎn)的下一個節(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)骄€性表中最后一個元素 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() { //鏈表為空鏈表時 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() { //鏈表為空鏈表時 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)比較
空間性能:
順序表:順序表的存儲空間是靜態(tài)分布的,需要一個長度固定的數(shù)組,因此總有部分?jǐn)?shù)組元素被浪費(fèi)。
鏈表:鏈表的存儲空間是動態(tài)分布的,因此不會空間浪費(fèi)。但是由于鏈表需要而外的空間來為每個節(jié)點(diǎn)保存指針,因此要犧牲一部分空間。
時間性能:
順序表:順序表中元素的邏輯順序與物理存儲順序是保持一致的,而且支持隨機(jī)存取。因此順序表在查找、讀取時性能很好。
鏈表:鏈表采用鏈?zhǔn)浇Y(jié)構(gòu)來保存表內(nèi)元素,因此在插入、刪除元素時性能要好
以上就是本文的全部內(nèi)容,希望對大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。
- Java實(shí)現(xiàn)線性表的鏈?zhǔn)酱鎯?/a>
- java實(shí)現(xiàn)線性表及其算法
- java 線性表接口的實(shí)例詳解
- Java數(shù)據(jù)結(jié)構(gòu)順序表從零基礎(chǔ)到精通進(jìn)階
- Java?精煉解讀數(shù)據(jù)結(jié)構(gòu)的順序表如何操作
- Java實(shí)現(xiàn)順序表和鏈表結(jié)構(gòu)
- Java實(shí)現(xiàn)順序表的操作
- Java數(shù)據(jù)結(jié)構(gòu)之順序表篇
- Java中ArrayList與順序表的概念與使用實(shí)例
- Java線性表的順序表示及實(shí)現(xiàn)
相關(guān)文章
springboot整合rocketmq實(shí)現(xiàn)分布式事務(wù)
大多數(shù)情況下很多公司是使用消息隊(duì)列的方式實(shí)現(xiàn)分布式事務(wù)。 本篇文章重點(diǎn)講解springboot環(huán)境下整合rocketmq實(shí)現(xiàn)分布式事務(wù),感興趣的可以了解一下2021-05-05Java關(guān)鍵字volatile知識點(diǎn)總結(jié)
在本篇文章里小編給大家整理的是一篇關(guān)于Java關(guān)鍵字volatile知識點(diǎn)總結(jié)內(nèi)容,有興趣的朋友們可以學(xué)習(xí)參考下。2021-01-01spring boot 配置動態(tài)刷新實(shí)現(xiàn)詳解
這篇文章主要介紹了spring boot 配置動態(tài)刷新實(shí)現(xiàn)詳解,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2019-09-09mybatis多對多查詢的實(shí)現(xiàn)(xml方式和注解方式)
本文主要介紹了mybatis多對多查詢的實(shí)現(xiàn),有xml方式和注解方式兩種,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2024-08-08