溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本篇文章為大家展示了深入淺析Java中的鏈表，內容簡明扼要并且容易理解，絕對能使你眼前一亮，通過這篇文章的詳細介紹希望你能有所收獲。
單鏈表：
insertFirst：在表頭插入一個新的鏈接點，時間復雜度為O(1)
deleteFirst：刪除表頭的鏈接點，時間復雜度為O(1)
find：查找包含指定關鍵字的鏈接點，由于需要遍歷查找，平均需要查找N/2次，即O(N)
remove：刪除包含指定關鍵字的鏈接點，由于需要遍歷查找，平均需要查找N/2次，即O(N)
public class LinkedList {
private class Data{
private Object obj;
private Data next = null;
Data(Object obj){
this.obj = obj;
}
}
private Data first = null;
public void insertFirst(Object obj){
Data data = new Data(obj);
data.next = first;
first = data;
}
public Object deleteFirst() throws Exception{
if(first == null)
throw new Exception("empty!");
Data temp = first;
first = first.next;
return temp.obj;
}
public Object find(Object obj) throws Exception{
if(first == null)
throw new Exception("LinkedList is empty!");
Data cur = first;
while(cur != null){
if(cur.obj.equals(obj)){
return cur.obj;
}
cur = cur.next;
}
return null;
}
public void remove(Object obj) throws Exception{
if(first == null)
throw new Exception("LinkedList is empty!");
if(first.obj.equals(obj)){
first = first.next;
}else{
Data pre = first;
Data cur = first.next;
while(cur != null){
if(cur.obj.equals(obj)){
pre.next = cur.next;
}
pre = cur;
cur = cur.next;
}
}
}
public boolean isEmpty(){
return (first == null);
}
public void display(){
if(first == null)
System.out.println("empty");
Data cur = first;
while(cur != null){
System.out.print(cur.obj.toString() + " -> ");
cur = cur.next;
}
System.out.print("\n");
}
public static void main(String[] args) throws Exception {
LinkedList ll = new LinkedList();
ll.insertFirst(4);
ll.insertFirst(3);
ll.insertFirst(2);
ll.insertFirst(1);
ll.display();
ll.deleteFirst();
ll.display();
ll.remove(3);
ll.display();
System.out.println(ll.find(1));
System.out.println(ll.find(4));
}
} 1 -> 2 -> 3 -> 4 -> 2 -> 3 -> 4 -> 2 -> 4 -> null 4
雙端鏈表(不是雙向鏈表)：
與單向鏈表的不同之處在保存有對最后一個鏈接點的引用(last)
insertFirst：在表頭插入一個新的鏈接點，時間復雜度O(1)
insertLast：在表尾插入一個新的鏈接點，時間復雜度O(1)
deleteFirst：刪除表頭的鏈接點，時間復雜度O(1)
deleteLast:：刪除表尾的鏈接點，由于只保存了表尾的鏈接點，而沒有保存表尾的前一個鏈接點(這里就體現出雙向鏈表的優勢了)，所以在刪除表尾鏈接點時需要遍歷以找到表尾鏈接點的前一個鏈接點，需查找N-1次，也就是O(N)
有了這幾個方法就可以用雙端鏈表來實現一個隊列了
public class FirstLastList {
private class Data{
private Object obj;
private Data next = null;
Data(Object obj){
this.obj = obj;
}
}
private Data first = null;
private Data last = null;
public void insertFirst(Object obj){
Data data = new Data(obj);
if(first == null)
last = data;
data.next = first;
first = data;
}
public void insertLast(Object obj){
Data data = new Data(obj);
if(first == null){
first = data;
}else{
last.next = data;
}
last = data;
}
public Object deleteFirst() throws Exception{
if(first == null)
throw new Exception("empty");
Data temp = first;
if(first.next == null)
last = null;
first = first.next;
return temp.obj;
}
public void deleteLast() throws Exception{
if(first == null)
throw new Exception("empty");
if(first.next == null){
first = null;
last = null;
}else{
Data temp = first;
while(temp.next != null){
if(temp.next == last){
last = temp;
last.next = null;
break;
}
temp = temp.next;
}
}
}
public void display(){
if(first == null)
System.out.println("empty");
Data cur = first;
while(cur != null){
System.out.print(cur.obj.toString() + " -> ");
cur = cur.next;
}
System.out.print("\n");
}
public static void main(String[] args) throws Exception {
FirstLastList fll = new FirstLastList();
fll.insertFirst(2);
fll.insertFirst(1);
fll.display();
fll.insertLast(3);
fll.display();
fll.deleteFirst();
fll.display();
fll.deleteLast();
fll.display();
}
} 1 -> 2 -> 1 -> 2 -> 3 -> 2 -> 3 -> 2 ->
有序鏈表：
鏈表中的數據按從小到大排列
public class SortedList {
private class Data{
private Object obj;
private Data next = null;
Data(Object obj){
this.obj = obj;
}
}
private Data first = null;
public void insert(Object obj){
Data data = new Data(obj);
Data pre = null;
Data cur = first;
while(cur != null && (Integer.valueOf(data.obj.toString())
.intValue() > Integer.valueOf(cur.obj.toString())
.intValue())){
pre = cur;
cur = cur.next;
}
if(pre == null)
first = data;
else
pre.next = data;
data.next = cur;
}
public Object deleteFirst() throws Exception{
if(first == null)
throw new Exception("empty!");
Data temp = first;
first = first.next;
return temp.obj;
}
public void display(){
if(first == null)
System.out.println("empty");
System.out.print("first -> last : ");
Data cur = first;
while(cur != null){
System.out.print(cur.obj.toString() + " -> ");
cur = cur.next;
}
System.out.print("\n");
}
public static void main(String[] args) throws Exception{
SortedList sl = new SortedList();
sl.insert(80);
sl.insert(2);
sl.insert(100);
sl.display();
System.out.println(sl.deleteFirst());
sl.insert(33);
sl.display();
sl.insert(99);
sl.display();
}
} first -> last : 2 -> 80 -> 100 -> 2 first -> last : 33 -> 80 -> 100 -> first -> last : 33 -> 80 -> 99 -> 100 ->
表的插入和刪除平均需要比較N/2次，即O(N)，但是獲取最小數據項只需O(1)，因為其始終處于表頭，對頻繁操作最小數據項的應用，可以考慮使用有序鏈表實現，如：優先級隊列和數組相比，鏈表的優勢在于長度不受限制，并且在進行插入和刪除操作時，不需要移動數據項，故盡管某些操作的時間復雜度與數組想同，實際效率上還是比數組要高很多。劣勢在于隨機訪問，無法像數組那樣直接通過下標找到特定的數據項 。
上述內容就是深入淺析Java中的鏈表，你們學到知識或技能了嗎？如果還想學到更多技能或者豐富自己的知識儲備，歡迎關注億速云行業資訊頻道。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
