博客主頁(4條訊息) 小吳_小吳有想法_CSDN博客-筆記,java,leetcode領域博主
歡迎關注
點贊
收藏和留言
天道酬勤，勤能補拙，和小吳一起加油吧
17歲大一新生，水平有限，懇請各位大佬指點，不勝感激!
- 參考書籍《演算法4》，學習視頻：黑馬程式員Java資料結構與java演算法，全網資料最全資料結構+演算法教程，154張java資料結構圖_嗶哩嗶哩_bilibili
目錄
線性表
順序表
代碼實作
時間復雜度
鏈表
單向鏈表
單向鏈表代碼實作
雙向鏈表
代碼實作
時間復雜度分析
線性表
線性表是最簡單，最基本，也是最常用的一種資料結構，一個線性表是n個具有相同特性的資料元素的有限序列，(一排高矮不同的人)
前驅元素：若A在B的前面，則稱A為B的前驅元素
后繼元素：若B在A的后面，則稱B為A的后驅元素
線性表的特征：
- 第一個資料元素沒有前驅，這個資料元素稱為"頭結點"
- 最后一個資料元素沒有后繼,這個資料元素稱為"尾結點"
- 除了第一個和最后一個資料元素外，其他資料元素有且僅有一個前綴和后綴
線性表用數學語言來定義，可表示為(a1,,,ai-1,ai,ai+1,,,an),ai-1是ai的前驅元素，ai+1是ai的后驅元素
線性表中資料的儲存方式的不同可以將線性表分為順序表和鏈表
順序表
順序表是在計算機記憶體中以陣列的形式保存的線性表，線性表的順序存盤是指用一組地址連續的儲存單元，依次存盤線性表中的各個元素，使得線性表中在邏輯結構中響鈴的資料元素存盤在相鄰的物理存盤單元中，即通過資料元素物理存盤的相鄰關系來反映資料元素之間邏輯上的相鄰關系
| 11 | 32 | 65 | 14 | 32 | 22 | 14 | 8 | 12 |
0 1 2 3 4 5 6 7 8
像這種陣列形式方便理解
順序表的代碼實作:
代碼實作
public class SequenceList<T> {
//存盤元素的陣列
private T[] a;
//記錄順序表中的元素個數
private int N;
//構造方法
public SequenceList(int capacity)
{ //初始化陣列
this.a=(T[])new Object[capacity];
this.N=0;
}
//將一個線性表置為空表
public void reset() {
this.N=0;
}
//判斷當前線性表是否為空表
public boolean isEmpty()
{
return N==0;
}
//獲取線性表的長度
public int length()
{
return N;
}
//獲取指定位置的元素
public T get(int i)
{
return a[i];
}
//向線性表中添加元素
public void insert(T t)
{
a[N++]=t;
}
//在i元素處插入元素t
public void insert(int i,T t)
{
//先把i索引處的元素及其后面索引處的元素依次向后移動一位
for(int index=N-1;index>i;index--)
{
a[index]=a[index-1];
}
//再把t元素放到i元素處即可
a[i]=t;
}
//洗掉指定位置i處的元素，并回傳該元素
public T remove(int i)
{
//記錄索引i處的值
T current=a[i];
//索引i后面的元素依次向前移動一位即可
for(int index= i;index<N-1;index++)
{
a[index]=a[index+1];
}
N--;
return current ;
}
//查找t元素第一次出現的位置
public int indexOf(T t)
{
for(int i=0;i<N;i++)
{
if(a[i]==t)
{
return i;
}
}
return -1;
}
public static void main(String[] args)
{
//創建順序表物件
SequenceList<String>s =new SequenceList<>(10);
//測驗插入
s.insert("姚明");
s.insert("小明");
s.insert("小王");
s.insert(1,"科比");
//測驗獲取
String gets=s.get(1);
System.out.println("索引1處的結果為:"+gets);
//測驗洗掉
String removeresult =s.remove(0);
System.out.println("洗掉的元素是:"+removeresult);
//測驗清空
s.reset();
System.out.println("清空后的元素個數為:"+s.length());
}
}
時間復雜度
- get(i):一次就可以獲取到對應的元素，時間復雜度為O(1);
- Insert(int i,T t):每一次插入，都需要把i位置后的元素移動一次，N越大，移動的元素越多，時間復雜度為O(N);
- remove(int i):每一次洗掉，都需要把i位置后面的元素移動一次，隨著資料量N的增大，移動的元素也越多，時間復雜度為O(N);
- 由于順序表的底層由陣列實作，陣列的長度是固定的，所以在操作的程序中涉及到了容器的擴容操作，這樣會導致順序表在使用程序中的時間復雜度不是線性的，在某些需要擴容的節點處，耗時會突增，尤其是元素越多，越明顯
鏈表
定義：鏈表是一種遞回的資料結構，它或者為空(null),或者是含有泛型元素的結點和指向另一條鏈表的參考，
鏈表是一種物理存盤單元上非連續，非順序的存盤結構，其物理結構不能直觀的表示資料元素的邏輯順序，資料元素的邏輯順序是通過鏈表中的指標鏈接次序實作的，鏈表由一系列的結點(鏈表中的每一個元素稱為結點)組成，結點可以在運行時動態生成，
我們可以設計一個類，用來描述結點這個事物，用一個屬性描述這個結點存盤的元素，用來另外一個屬性描述這個結點的下一個結點，
| 類名 | Node<T> |
| 構造方法 | Node(T t,Node next):創建Node物件 |
| 成員變數 | T item:存盤資料 Node next:指向下一個結點 |
public class Node<T> {
//存盤元素
public T item;
//指向下一個結點
public Node next;
public Node(T item,Node next)
{
this.item=item;
this.next=next;
}
public static void main(String[] args)
{
//構建結點
Node<Integer>first=new Node<Integer>(10,null);
Node<Integer>second=new Node<Integer>(20,null);
Node<Integer>third=new Node<Integer>(30,null);
//生成鏈表
first.next=second;
second.next=third;
}
}
單向鏈表
單向鏈表是鏈表的一種，它由多個結點組成，每個結點都由一個資料域和一個指標域組成，資料域用來存盤資料，指標域用來指向其后繼結點，鏈表的頭結點的資料域不存盤資料，指標域指向第一個真正存盤資料的結點，
單向鏈表代碼實作
import java.util.Iterator; //Iterable介面用來表面可以進行迭代
public class LinkList<T> implements Iterable<T> {
//記錄頭結點
private Node head;
//記錄鏈表的長度
private int N;
//結點類
private class Node{
//存盤資料
T item;
//下一個結點
Node next;
public Node(T item,Node next)
{
this.item=item;
this.next=next;
}
}
public LinkList() {
//創建結節點
this.head=new Node(null,null);
//初始化元素個數
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)
{
//通過回圈，從頭結點開始往后找，依次找i次，就可以找到對應的元素
Node n=head.next;//不斷的把n向后變化，直到變化到第i個位置處
for(int index=0;index<i;index++)
{
n=n.next;
}
return n.item;
}
//向鏈表中添加元素t
public void insert(T t)
{
//找到當前最后一個結點
Node n=head;
while(n.next!=null)
{
n=n.next;
}
//創建新結點，保存元素t
Node newNode =new Node(t,null);
//讓當前最后一個結點指向新結點
n.next=newNode;
//元素的個數加1
N++;
}
//向指定位置i處，添加元素t
public void insert(int i,T t)
{
//找到i位置前一個節點
Node p=head;
for(int index=0;index<=i-1;index++)
{
p=p.next;
}
//找到i位置的節點
Node c=p.next;
//創建新結點,并且新結點需要指向原來i位置的結點
Node newNode =new Node(t,c);
//原來i位置的前一個結點指向新結點即可
p.next=newNode;
//元素的個數+1
N++;
}
//洗掉指定位置i處的元素，并回傳被洗掉的元素
public T remove(int i)
{
//找到i位置的前一個結點
Node p=head;
for(int index=0;index<=i-1;i++)
{
p=p.next;
}
//要找到i位置的結點
Node c=p.next;
//找到i位置的下一個結點
Node nextNode=c.next;
//前一個節點指向下一個結點
p.next=nextNode;
//元素個數減1
N--;
return c.item;
}
//查找元素t在鏈表中第一次出現的位置
public int indexOf(T t)
{
//從頭結點開始，依次找到每一個結點，取出item,和t比較，如果相同，就找到了
Node n=head;
for(int index=0;n.next!=null;index++)
{
n=n.next;
if(n.item==t)
return index;
}
return -1;
}
public Iterator<T> iterator()
{
return new LIterator();
}
private class LIterator implements Iterator{
private Node n;
public LIterator()
{
this.n=head;
}
@Override
public boolean hasNext() {
return n.next!=null;
}
@Override
public Object next()
{
n=n.next;
return n.item;
}
}
}
import java.util.Arrays;
public class test{
public static void main(String[] args)
{
//創建單向鏈表物件
LinkList <String> s1= new LinkList<>();
//測驗插入
s1.insert("姚明");
s1.insert("科比");
s1.insert("小王");
s1.insert(1,"成龍");
for(String s:s1)
{
System.out.println(s);
}
System.out.println("————————————————————————————————————————————————————");
//測驗獲取
String getresult =s1.get(1);
System.out.println("獲取索引1處的結果為:"+getresult);
//測驗洗掉
String removeresult =s1.remove(0);
System.out.println("洗掉元素是:"+removeresult);
//測驗清空
s1.clear();
System.out.println("清空后的線性表中的元素個數為:"+s1.length());
}
}
雙向鏈表
定義：雙向鏈表也叫雙向表，是鏈表的一種，它由多個結點組成，每個結點都由一個資料域和兩個指標域組成，資料域用來存盤資料，其中一個指標域用來指向其后繼結點，另一個指標域用來指向前驅結點，鏈表的頭結點的資料域不存盤資料，指向前驅結點的指標域值為null，指向后繼結點的指標域指向第一個真正存盤資料的結點，
代碼實作
import java.util.Iterator;
//Iterable介面用來表面可以進行迭代
public class TowWayLinkList<T> implements Iterable<T> {
//首結點
private Node head;
//尾結點
private Node last;
//鏈表的長度
private int N;
//結點類
private class Node{
//存盤資料
public T item;
//指向上一個結點
public Node pre;
//指向下一個結點
public Node next;
public Node(T item,Node pre,Node next)
{
this.item=item;
this.next=next;
this.pre=pre;
}
}
public TowWayLinkList()
{
//初始化頭結點和尾結點
this.head=new Node(null,null,null);
this.last=null;//剛開始尾結點沒有資料
//初始化元素個數
this.N=0;
}
//清空鏈表
public void clear()
{
this.head.next=null;
this.head.item=null;
this.head.pre=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;
}
//插入元素t
public void insert(T t)
{
//如果鏈表為空,1.創建新的結點，2.并讓新結點成為尾結點，3.并讓頭結點指向新結點
if(isEmpty())
{
//1.創建新結點
Node newNode=new Node(t,head,null);
//2.讓新結點成為尾結點
last=newNode;
//3.讓頭結點指向新結點
head.next=last;
}
else//如果鏈表不為空
{
//創建新的結點
Node oldlast=last;
Node newNode=new Node(t,oldlast,null);
//讓當前的尾結點指向新結點
oldlast.next=newNode;
//讓新結點稱為尾結點
last=newNode;
}
N++;//元素個數加1
}
//向指定位置i處插入元素t
public void insert(int i,T t)
{
//找到i位置的前一個結點
Node pre=head;
for(int index=0;index<=i-1;index++)
{
pre=pre.next;
}
//找到i位置的結點
Node c=pre.next;
//創建新結點
Node newNode=new Node(t,pre,c);
//讓i位置的前一個結點的下一個結點變為新結點
pre.next=newNode;
//讓i位置的前一個結點變為新結點
c.pre=newNode;
//元素個數+1
N++;
}
public T get(int i)
{
Node n=head.next;
for(int index=0;index<i;index++)
{
n=n.next;
}
return n.item;
}
//找到元素t在鏈表中第一次出現的位置
public int indexOf(T t)
{
//從頭結點開始，依次找到每一個結點，取出item,和t比較，如果相同，就找到了
Node n=head;
for(int index=0;n.next!=null;index++)
{
n=n.next;
if(n.item==t)
return index;
}
return -1;
}
//洗掉指定位置i處的元素，并回傳被洗掉的元素
public T remove(int i)
{
//找到i位置的前一個結點
Node pre=head;
for(int index=0;index<=i-1;i++)
{
pre=pre.next;
}
//要找到i位置的結點
Node c=pre.next;
//找到i位置的下一個結點
Node nextNode=c.next;
//讓i位置的前一個結點的下一個結點變為i位置的下一個結點
pre.next=nextNode;
//讓i位置的后一個節點的上一個結點變為i位置的上一個結點
nextNode.pre=pre;
//元素個數減1
N--;
return c.item;
}
@Override
public Iterator<T> iterator() {
// TODO Auto-generated method stub
return new TIterator();
}
private class TIterator implements Iterator{
private Node n;
public TIterator()
{
this.n=head;
}
@Override
public boolean hasNext() {
return n.next!=null;
}
@Override
public Object next()
{
n=n.next;
return n.item;
}
}
}import java.util.Arrays;
public class test{
public static void main(String[] args)
{
//創建雙向鏈表物件
TowWayLinkList <String> s1= new TowWayLinkList<>();
//測驗插入
s1.insert("姚明");
s1.insert("科比");
s1.insert("小王");
s1.insert(1,"成龍");
for(String s:s1)
{
System.out.println(s);
}
System.out.println("——————————————————————————————————————————————————");
System.out.println("第一個元素是"+s1.getFirst());
System.out.println("第后一個元素是"+s1.getLast());
System.out.println("————————————————————————————————————————————————————");
//測驗獲取
String getresult =s1.get(1);
System.out.println("獲取索引1處的結果為:"+getresult);
//測驗洗掉
String removeresult =s1.remove(0);
System.out.println("洗掉元素是:"+removeresult);
//測驗清空
s1.clear();
System.out.println("清空后的線性表中的元素個數為:"+s1.length());
}
}
時間復雜度分析
視頻筆記：
- get(int i)：每一次查詢，都需要從鏈表的頭部開始，依次向后查找，隨著資料元素N的增多，比較的元素越多，時間復雜度為O(n)
- insert(int i,T t):每一次插入，需要先找到i位置的前一個元素，然后完成插入操作，隨著資料元素N的增多，查找的元素越多，時間復雜度為O(n)
- remove(int i):每一次移除，需要先找到i位置的前一個元素，然后完成插入操作，隨著資料元素N的增多，查找的元素越多，時間復雜度為O(n)
- 相比較順序表，鏈表插入和洗掉的時間復雜度雖然一樣，但仍然有很大的優勢，因為鏈表的物理地址是不連續的，它不需要預先指定存盤空間的大小，或者在存盤程序中涉及到擴容等操作，同時它并沒有涉及的元素的交換
- 相比較順序表，鏈表的查詢操作性能會比較低，因此，如果我們的程式中查詢的操作比較多，建議使用順序表，增刪操作比較多，建議使用鏈表
學習如逆水行舟，不進則退，和小吳一起加油吧！
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/413894.html
標籤：java