文章目錄

• • 線性表
  • 順序表
  • • 順序表API設(shè)計
    • 順序表的代碼實現(xiàn)
  • 鏈表
  • • 單向鏈表
    • 雙向鏈表
  • 總結(jié)

線性表

概述

• 線性表是最基本、最簡單、也是最常用的一種數(shù)據(jù)結(jié)構(gòu)。
• 一個線性表是n個具有相同特性的數(shù)據(jù)元素的有限序列。

先驅(qū)元素: 若A元素在B元素的前面，則稱A為B的前驅(qū)元素
后繼元素： 若B元素在A元素的后面，則稱B為A的后繼元素
線性表的特征： 數(shù)據(jù)元素之間具有一種“一對一”的邏輯關(guān)系。

• 第一個數(shù)據(jù)元素沒有前驅(qū)，這個數(shù)據(jù)元素被稱為頭結(jié)點；
• 最后一個數(shù)據(jù)元素沒有后繼，這個數(shù)據(jù)元素被稱為尾結(jié)點；
• 除了第一個和最后一個數(shù)據(jù)元素外，其他數(shù)據(jù)元素有且僅有一個前驅(qū)和一個后繼

線性表的分類：
線性表中數(shù)據(jù)存儲的方式可以是順序存儲，也可以是鏈式存儲，按照數(shù)據(jù)的存儲方式不同，可以把線性表分為順序
表和鏈表。

順序表

概述:

• 順序表是在計算機內(nèi)存中以數(shù)組的形式保存的線性表
• 線性表的順序存儲是指用一組地址連續(xù)的存儲單元，依次存儲線性表中的各個元素、使得線性表中再邏輯結(jié)構(gòu)上響鈴的數(shù)據(jù)元素存儲在相鄰的物理存儲單元中
• 即通過數(shù)據(jù)元素物理存儲的相鄰關(guān)系來反映數(shù)據(jù)元素之間邏輯上的相鄰關(guān)系。

順序表API設(shè)計

順序表類名SequenceList：

• 構(gòu)造方法：SequenceList(int capacity)：創(chuàng)建容量為capacity的SequenceList對象
• 成員變量：
  1.private T[] eles：存儲元素的數(shù)組
  2.private int N:當前線性表的長度
• 成員方法
  1.public void clear()：空置線性表
  2.publicboolean isEmpty()：判斷線性表是否為空，是返回true，否返回false
  3.public int length():獲取線性表中元素的個數(shù)
  4.public T get(int i):讀取并返回線性表中的第i個元素的值
  5.public void insert(int i,T t)：在線性表的第i個元素之前插入一個值為t的數(shù)據(jù)元素。
  6.public void insert(T t):向線性表中添加一個元素t
  7.public T remove(int i):刪除并返回線性表中第i個數(shù)據(jù)元素。
  8.public int indexOf(T t):返回線性表中首次出現(xiàn)的指定的數(shù)據(jù)元素的位序號，若不存在，則返
  回-1.

順序表的代碼實現(xiàn)

import java.util.Iterator;public class SequenceList<T> implements Iterable<T>{//存儲元素的數(shù)組private T[] eles;//記錄當前順序表中的元素個數(shù)private int N;//構(gòu)造方法public SequenceList(int capacity){//初始化數(shù)組this.eles=(T[])new Object[capacity];//初始化長度this.N=0;}//將一個線性表置為空表public void clear(){this.N=0;}//判斷當前線性表是否為空表public boolean isEmpty(){return N==0;}//獲取線性表的長度public int length(){return N;}//獲取指定位置的元素public T get(int i){return eles[i];}//向線型表中添加元素tpublic void insert(T t){if (N==eles.length){resize(2*eles.length);}eles[N++]=t;}//在i元素處插入元素tpublic void insert(int i,T t){if (N==eles.length){resize(2*eles.length);}//先把i索引處的元素及其后面的元素依次向后移動一位for(int index=N;index>i;index--){eles[index]=eles[index-1];}//再把t元素放到i索引處即可eles[i]=t;//元素個數(shù)+1N++;}//刪除指定位置i處的元素，并返回該元素public T remove(int i){//記錄索引i處的值T current = eles[i];//索引i后面元素依次向前移動一位即可for(int index=i;index<N-1;index++){eles[index]=eles[index+1];}//元素個數(shù)-1N--;if (N<eles.length/4){resize(eles.length/2);}return current;}//查找t元素第一次出現(xiàn)的位置public int indexOf(T t){for(int i=0;i<N;i++){if (eles[i].equals(t)){return i;}}return -1;}//根據(jù)參數(shù)newSize，重置eles的大小public void resize(int newSize){//定義一個臨時數(shù)組，指向原數(shù)組T[] temp=eles;//創(chuàng)建新數(shù)組eles=(T[])new Object[newSize];//把原數(shù)組的數(shù)據(jù)拷貝到新數(shù)組即可for(int i=0;i<N;i++){eles[i]=temp[i];}}@Overridepublic Iterator<T> iterator() {return new SIterator();}private class SIterator implements Iterator{private int cusor;public SIterator(){this.cusor=0;}@Overridepublic boolean hasNext() {return cusor<N;}@Overridepublic Object next() {return eles[cusor++];}} } //測試環(huán)節(jié) public class SequenceListTest {public static void main(String[] args) {//創(chuàng)建順序表對象SequenceList<String> sl = new SequenceList<>(10);//測試插入sl.insert("王仙芝");sl.insert("劍九黃");sl.insert("李淳罡");sl.insert(1,"徐鳳年");for (String s : sl) {System.out.println(s);}//測試獲取String getResult = sl.get(1);System.out.println("獲取索引1處的結(jié)果為："+getResult);//測試刪除String removeResult = sl.remove(0);System.out.println("刪除的元素是："+removeResult);//測試清空sl.clear();System.out.println("清空后的線性表中的元素個數(shù)為:"+sl.length());} }

鏈表

概述：

• 鏈表是一種物理存儲單元上非連續(xù)、非順序的存儲結(jié)構(gòu)，其物理結(jié)構(gòu)不能只管的表示數(shù)據(jù)元素的邏輯順序，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的
• 鏈表由一系列的結(jié)點（鏈表中的每一個元素稱為結(jié)點）組成，結(jié)點可以在運行時動態(tài)生成。

結(jié)點API設(shè)計

類名Node

構(gòu)造方法	Node(T t,Node next)： 創(chuàng)建Node對象
成員變量	T item：存儲數(shù)據(jù) Node next：指向下一個結(jié)點

實現(xiàn)結(jié)點類

public class Node<T> { //存儲元素 public T item; //指向下一個結(jié)點 public Node next; public Node(T item, Node next) {this.item = item;this.next = next; } }

生成鏈表：

public static void main(String[] args) throws Exception { //構(gòu)建結(jié)點 Node<Integer> first = new Node<Integer>(11, null); Node<Integer> second = new Node<Integer>(13, null); Node<Integer> third = new Node<Integer>(12, null); Node<Integer> fourth = new Node<Integer>(8, null); Node<Integer> fifth = new Node<Integer>(9, null); //生成鏈表 first.next = second; second.next = third; third.next = fourth; fourth.next = fifth; }

單向鏈表

概述：

• 單向鏈表是鏈表的一種，它由多個結(jié)點組成，每個結(jié)點都由一個數(shù)據(jù)域和一個指針域組成，數(shù)據(jù)域用來存儲數(shù)據(jù)，指針域用來指向其后繼結(jié)點。
• 鏈表的頭結(jié)點的數(shù)據(jù)域不存儲數(shù)據(jù)，指針域指向第一個真正存儲數(shù)據(jù)的結(jié)點。
  

單向鏈表LinkList類：

• 構(gòu)造方法：LinkList()：創(chuàng)建LinkList對象
• 成員方法：
  1.public void clear()：空置線性表
  2.publicboolean isEmpty()：判斷線性表是否為空，是返回true，否返回false
  3.public int length():獲取線性表中元素的個數(shù)
  4.public T get(int i):讀取并返回線性表中的第i個元素的值
  5.public void insert(T t)：往線性表中添加一個元素；
  6.public void insert(int i,T t)：在線性表的第i個元素之前插入一個值為t的數(shù)據(jù)元素。
  7.public T remove(int i):刪除并返回線性表中第i個數(shù)據(jù)元素。
  8.public int indexOf(T t):返回線性表中首次出現(xiàn)的指定的數(shù)據(jù)元素的位序號，若不存在，則
  返回-1。
• 成員內(nèi)部類：private class Node:結(jié)點類
• 成員變量：
  1.private Node head:記錄首結(jié)點
  2.private int N:記錄鏈表的長度
  單向鏈表的代碼演示

import java.util.Iterator; public class LinkList<T> implements Iterable<T>{//記錄頭結(jié)點private Node head;//記錄鏈表的長度private int N;//結(jié)點類private class Node {//存儲數(shù)據(jù)T item;//下一個結(jié)點Node next;public Node(T item, Node next) {this.item = item;this.next = next;}}public LinkList() {//初始化頭結(jié)點、this.head = new Node(null,null);//初始化元素個數(shù)this.N=0;}//清空鏈表public void clear() {head.next=null;this.N=0;}//獲取鏈表的長度public int length() {return N;}//判斷鏈表是否為空public boolean isEmpty() {return N==0;}//獲取指定位置i出的元素public T get(int i) {//通過循環(huán),從頭結(jié)點開始往后找，依次找i次，就可以找到對應(yīng)的元素Node n = head.next;for(int index=0;index<i;index++){n=n.next;}return n.item;}//向鏈表中添加元素tpublic void insert(T t) {//找到當前最后一個結(jié)點Node n = head;while(n.next!=null){n=n.next;}//創(chuàng)建新結(jié)點，保存元素tNode newNode = new Node(t, null);//讓當前最后一個結(jié)點指向新結(jié)點n.next=newNode;//元素的個數(shù)+1N++;}//向指定位置i出，添加元素tpublic void insert(int i, T t) {//找到i位置前一個結(jié)點Node pre = head;for(int index=0;index<=i-1;index++){pre=pre.next;}//找到i位置的結(jié)點Node curr = pre.next;//創(chuàng)建新結(jié)點，并且新結(jié)點需要指向原來i位置的結(jié)點Node newNode = new Node(t, curr);//原來i位置的前一個節(jié)點指向新結(jié)點即可pre.next=newNode;//元素的個數(shù)+1N++;}//刪除指定位置i處的元素，并返回被刪除的元素public T remove(int i) {//找到i位置的前一個節(jié)點Node pre = head;for(int index=0;index<=i-1;i++){pre=pre.next;}//要找到i位置的結(jié)點Node curr = pre.next;//找到i位置的下一個結(jié)點Node nextNode = curr.next;//前一個結(jié)點指向下一個結(jié)點pre.next=nextNode;//元素個數(shù)-1N--;return curr.item;}//查找元素t在鏈表中第一次出現(xiàn)的位置public int indexOf(T t) {//從頭結(jié)點開始，依次找到每一個結(jié)點，取出item，和t比較，如果相同，就找到了Node n = head;for(int i=0;n.next!=null;i++){n=n.next;if (n.item.equals(t)){return i;}}return -1;}@Overridepublic Iterator<T> iterator() {return new LIterator();}private class LIterator implements Iterator{private Node n;public LIterator(){this.n=head;}@Overridepublic boolean hasNext() {return n.next!=null;}@Overridepublic Object next() {n = n.next;return n.item;}}//用來反轉(zhuǎn)整個鏈表public void reverse(){//判斷當前鏈表是否為空鏈表，如果是空鏈表，則結(jié)束運行，如果不是，則調(diào)用重載的reverse方法完成反轉(zhuǎn)if (isEmpty()){return;}reverse(head.next);}//反轉(zhuǎn)指定的結(jié)點curr，并把反轉(zhuǎn)后的結(jié)點返回public Node reverse(Node curr){if (curr.next==null){head.next=curr;return curr;}//遞歸的反轉(zhuǎn)當前結(jié)點curr的下一個結(jié)點；返回值就是鏈表反轉(zhuǎn)后，當前結(jié)點的上一個結(jié)點Node pre = reverse(curr.next);//讓返回的結(jié)點的下一個結(jié)點變?yōu)楫斍敖Y(jié)點curr；pre.next=curr;//把當前結(jié)點的下一個結(jié)點變?yōu)閚ullcurr.next=null;return curr;} //測試代碼 public static void main(String[] args) {//創(chuàng)建順序表對象LinkList<String> sl = new LinkList<>();//測試插入sl.insert("王仙芝");sl.insert("劍九黃");sl.insert("李淳罡");sl.insert(1,"徐鳳年");for (String s : sl) {System.out.println(s);}System.out.println("------------------------------------------");//測試獲取String getResult = sl.get(1);System.out.println("獲取索引1處的結(jié)果為："+getResult);//測試刪除String removeResult = sl.remove(0);System.out.println("刪除的元素是："+removeResult);//測試清空sl.clear();System.out.println("清空后的線性表中的元素個數(shù)為:"+sl.length());}}

雙向鏈表

概述：

• 雙向鏈表也叫雙向表，是鏈表的一種，它由多個結(jié)點組成，每個結(jié)點都由一個數(shù)據(jù)域和兩個指針域組成，數(shù)據(jù)域用來存儲數(shù)據(jù)，其中一個指針域用來指向其后繼結(jié)點，另一個指針域用來指向前驅(qū)結(jié)點。
• 鏈表的頭結(jié)點的數(shù)據(jù)域不存儲數(shù)據(jù)，指向前驅(qū)結(jié)點的指針域值為null，指向后繼結(jié)點的指針域指向第一個真正存儲數(shù)據(jù)的結(jié)點。
  雙向鏈表TowWayLinkList類
• 構(gòu)造方法：TowWayLinkList()：創(chuàng)建TowWayLinkList對象
• 成員方法：
  1.public void clear()：空置線性表
  2.publicboolean isEmpty()：判斷線性表是否為空，是返回true，否返回false
  3.public int length():獲取線性表中元素的個數(shù)
  4.public T get(int i):讀取并返回線性表中的第i個元素的值
  5.public void insert(T t)：往線性表中添加一個元素；
  6.public void insert(int i,T t)：在線性表的第i個元素之前插入一個值為t的數(shù)據(jù)元素。
  7.public T remove(int i):刪除并返回線性表中第i個數(shù)據(jù)元素。
  8.public int indexOf(T t):返回線性表中首次出現(xiàn)的指定的數(shù)據(jù)元素的位序號，若不存在，則
  返回-1。
  9.public T getFirst():獲取第一個元素
  10.public T getLast():獲取最后一個元素
• 成員內(nèi)部類：private class Node:結(jié)點類
• 成員變量：
  1.private Node first:記錄首結(jié)點
  2.private Node last:記錄尾結(jié)點
  2.private int N:記錄鏈表的長度
  雙向鏈表代碼演示

import java.util.Iterator; public class TowWayLinkList<T> implements Iterable<T> {//首結(jié)點private Node head;//最后一個結(jié)點private Node last;//鏈表的長度private int N;//結(jié)點類private class Node{public Node(T item, Node pre, Node next) {this.item = item;this.pre = pre;this.next = next;}//存儲數(shù)據(jù)public T item;//指向上一個結(jié)點public Node pre;//指向下一個結(jié)點public Node next;}public TowWayLinkList() {//初始化頭結(jié)點和尾結(jié)點this.head = new Node(null,null,null);this.last=null;//初始化元素個數(shù)this.N=0;}//清空鏈表public void clear(){this.head.next=null;this.head.pre=null;this.head.item=null;this.last=null;this.N=0;}//獲取鏈表長度public int length(){return N;}//判斷鏈表是否為空public boolean isEmpty(){return N==0;}//獲取第一個元素public T getFirst(){if (isEmpty()){return null;}return head.next.item;}//獲取最后一個元素public T getLast(){if (isEmpty()){return null;}return last.item;}//插入元素tpublic void insert(T t){if (isEmpty()){//如果鏈表為空：//創(chuàng)建新的結(jié)點Node newNode = new Node(t,head, null);//讓新結(jié)點稱為尾結(jié)點last=newNode;//讓頭結(jié)點指向尾結(jié)點head.next=last;}else {//如果鏈表不為空Node oldLast = last;//創(chuàng)建新的結(jié)點Node newNode = new Node(t, oldLast, null);//讓當前的尾結(jié)點指向新結(jié)點oldLast.next=newNode;//讓新結(jié)點稱為尾結(jié)點last = newNode;}//元素個數(shù)+1N++;}//向指定位置i處插入元素tpublic void insert(int i,T t){//找到i位置的前一個結(jié)點Node pre = head;for(int index=0;index<i;index++){pre=pre.next;}//找到i位置的結(jié)點Node curr = pre.next;//創(chuàng)建新結(jié)點Node newNode = new Node(t, pre, curr);//讓i位置的前一個結(jié)點的下一個結(jié)點變?yōu)樾陆Y(jié)點pre.next=newNode;//讓i位置的前一個結(jié)點變?yōu)樾陆Y(jié)點curr.pre=newNode;//元素個數(shù)+1N++;}//獲取指定位置i處的元素public T get(int i){Node n = head.next;for(int index=0;index<i;index++){n=n.next;}return n.item;}//找到元素t在鏈表中第一次出現(xiàn)的位置public int indexOf(T t){Node n = head;for(int i=0;n.next!=null;i++){n=n.next;if (n.next.equals(t)){return i;}}return -1;}//刪除位置i處的元素，并返回該元素public T remove(int i){//找到i位置的前一個結(jié)點Node pre = head;for(int index=0;index<i;index++){pre=pre.next;}//找到i位置的結(jié)點Node curr = pre.next;//找到i位置的下一個結(jié)點Node nextNode= curr.next;//讓i位置的前一個結(jié)點的下一個結(jié)點變?yōu)閕位置的下一個結(jié)點pre.next=nextNode;//讓i位置的下一個結(jié)點的上一個結(jié)點變?yōu)閕位置的前一個結(jié)點nextNode.pre=pre;//元素的個數(shù)-1N--;return curr.item;}@Overridepublic Iterator<T> iterator() {return new TIterator();}private class TIterator implements Iterator{private Node n;public TIterator(){this.n=head;}@Overridepublic boolean hasNext() {return n.next!=null;}@Overridepublic Object next() {n=n.next;return n.item;}} } //測試類 public class TowWayLinkListTest {public static void main(String[] args) {//創(chuàng)建雙向鏈表對象TowWayLinkList<String> sl = new TowWayLinkList<>();//測試插入sl.insert("姚明");sl.insert("科比");sl.insert("麥迪");sl.insert(1,"詹姆斯");for (String s : sl) {System.out.println(s);} System.out.println("第一個元素是："+sl.getFirst());System.out.println("最后一個元素是："+sl.getLast()); //測試獲取String getResult = sl.get(1);System.out.println("獲取索引1處的結(jié)果為："+getResult);//測試刪除String removeResult = sl.remove(0);System.out.println("刪除的元素是："+removeResult);//測試清空sl.clear();System.out.println("清空后的線性表中的元素個數(shù)為:"+sl.length());}

總結(jié)

順序表與鏈表的比較：

• 相比鏈表 ，順序表的插入效率比較低，而定義數(shù)組大小也是固定的，有時候通過擴容的方法使耗時突增，如果查找的比較多，建議使用順序表。
• 相比順序表，鏈表的查詢操作性能會比較低。因此，如果我們的程序中查詢操作比較多，建議使用順序表，增刪操作比較多，建議使用鏈表。

總結(jié)

以上是生活随笔為你收集整理的Java数据结构与算法_线性表_顺序表与链表的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。