資訊專欄INFORMATION COLUMN
摘要：鏈?zhǔn)酱鎯Y(jié)構(gòu)的線性表將采用一組任意的存儲單元存放線性表中的數(shù)據(jù)元素。三單向鏈表的實(shí)現(xiàn)下面的程序分別實(shí)現(xiàn)了線性表的初始化獲取線性表長度獲取指定索引處元素根據(jù)值查找插入刪除清空等操作。
文章有不當(dāng)之處，歡迎指正，如果喜歡微信閱讀，你也可以關(guān)注我的微信公眾號：好好學(xué)java，獲取優(yōu)質(zhì)學(xué)習(xí)資源。一、概述
單向鏈表（單鏈表）是鏈表的一種，其特點(diǎn)是鏈表的鏈接方向是單向的，對鏈表的訪問要通過順序讀取從頭部開始。
鏈?zhǔn)酱鎯Y(jié)構(gòu)的線性表將采用一組任意的存儲單元存放線性表中的數(shù)據(jù)元素。由于不需要按順序存儲，鏈表在插入、刪除數(shù)據(jù)元素時比順序存儲要快，但是在查找一個節(jié)點(diǎn)時則要比順序存儲要慢
使用鏈?zhǔn)酱鎯梢钥朔樞蚓€性表需要預(yù)先知道數(shù)據(jù)大小的缺點(diǎn)，鏈表結(jié)構(gòu)可以充分利用內(nèi)存空間，實(shí)現(xiàn)靈活的內(nèi)存動態(tài)管理。但是鏈?zhǔn)酱鎯κチ藬?shù)組隨機(jī)存取的特點(diǎn)，同時增加了節(jié)點(diǎn)的指針域，空間開銷較大。
二、圖解下圖就是最簡單最一般的單向鏈表：
將值為element的新節(jié)點(diǎn)插入到第index的位置上。
首先要先找到索引為index-1的節(jié)點(diǎn)，然后生成一個數(shù)據(jù)為element的新節(jié)點(diǎn)newNode，并令index-1處節(jié)點(diǎn)的next指向新節(jié)點(diǎn)，新節(jié)點(diǎn)的next指向原來index處的節(jié)點(diǎn)。
刪除第index個節(jié)點(diǎn)，第index節(jié)點(diǎn)是由index-1出的節(jié)點(diǎn)引用的，因此刪除index的節(jié)點(diǎn)要先獲取index-1處的節(jié)點(diǎn)，然后讓index-1出節(jié)點(diǎn)的next引用到原index+1處的節(jié)點(diǎn)，并釋放index處節(jié)點(diǎn)即可。
三、單向鏈表的Java實(shí)現(xiàn)下面的程序分別實(shí)現(xiàn)了線性表的初始化、獲取線性表長度、獲取指定索引處元素、根據(jù)值查找、插入、刪除、清空等操作。
public class LinkList四、測試代碼{ // 定義一個內(nèi)部類Node，代表鏈表的節(jié)點(diǎn) private class Node { private T data;// 保存數(shù)據(jù) private Node next;// 指向下個節(jié)點(diǎn)的引用 // 無參構(gòu)造器 public Node() { } // 初始化全部屬性的構(gòu)造器 public Node(T data, Node next) { this.data = data; this.next = next; } } private Node header;// 保存頭結(jié)點(diǎn) private Node tail;// 保存尾節(jié)點(diǎn) private int size;// 保存已含有的節(jié)點(diǎn)數(shù) // 創(chuàng)建空鏈表 public LinkList() { header = null; tail = null; } // 已指定數(shù)據(jù)元素創(chuàng)建鏈表，只有一個元素 public LinkList(T element) { header = new Node(element, null); // 只有一個節(jié)點(diǎn)，header,tail都指向該節(jié)點(diǎn) tail = header; size++; } // 返回鏈表的長度 public int length() { return size; } // 獲取指定索引處的元素 public T get(int index) { return this.getNodeByIndex(index).data; } //獲取指定位置的節(jié)點(diǎn) private Node getNodeByIndex(int index){ if(index < 0 || index > size-1){ throw new IndexOutOfBoundsException("索引超出線性表范圍"); } Node current = header;//從header開始遍歷 for(int i=0; i size){ throw new IndexOutOfBoundsException("索引超出線性表范圍"); } //如果是空鏈表 if(header == null){ add(element); } else{ //當(dāng)index為0時，即在鏈表頭處插入 if(0 == index){ addAtHead(element); } else{ Node prev = getNodeByIndex(index - 1);//獲取前一個節(jié)點(diǎn) //讓prev的next指向新節(jié)點(diǎn)，新節(jié)點(diǎn)的next指向原來prev的下一個節(jié)點(diǎn) prev.next = new Node(element, prev.next); size++; } } } //在尾部插入元素 public void add(T element) { //如果鏈表是空的 if(header == null){ header = new Node(element, null); //只有一個節(jié)點(diǎn)，headwe,tail都該指向該節(jié)點(diǎn) tail = header; } else{ Node newNode = new Node(element, null);//創(chuàng)建新節(jié)點(diǎn) tail.next = newNode;//尾節(jié)點(diǎn)的next指向新節(jié)點(diǎn) tail = newNode;//將新節(jié)點(diǎn)作為尾節(jié)點(diǎn) } size++; } //頭部插入 public void addAtHead(T element){ //創(chuàng)建新節(jié)點(diǎn)，讓新節(jié)點(diǎn)的next指向header //并以新節(jié)點(diǎn)作為新的header Node newNode = new Node(element, null); newNode.next = header; header = newNode; //若插入前是空表 if(tail == null){ tail = header; } size++; } //刪除指定索引處的元素 public T delete(int index){ if(index < 0 || index > size-1){ throw new IndexOutOfBoundsException("索引超出線性表范圍"); } Node del = null; //若要刪除的是頭節(jié)點(diǎn) if(index == 0){ del = header; header = header.next; } else{ Node prev = getNodeByIndex(index - 1);//獲取待刪除節(jié)點(diǎn)的前一個節(jié)點(diǎn) del = prev.next;//獲取待刪除節(jié)點(diǎn) prev.next = del.next; del.next = null;//將被刪除節(jié)點(diǎn)的next引用置為空 } size--; return del.data; } //刪除最后一個元素 public T remove(){ return delete(size - 1); } //判斷線性表是否為空 public boolean isEmpty(){ return size == 0; } //清空線性表 public void clear(){ //將header,tail置為null header = null; tail = null; size = 0; } public String toString(){ if(isEmpty()){ 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(); } } }
import org.junit.Test;
import com.sihai.algorithm.LinkList;
public class LinkListTest {
@Test
public void test() {
// 測試構(gòu)造函數(shù)
LinkList list = new LinkList("好");
System.out.println(list);
// 測試添加元素
list.add("放大");
list.add("沒");
System.out.println(list);
// 在頭部添加
list.addAtHead("啦啦啦");
System.out.println(list);
// 在指定位置添加
list.insert("膜拜", 2);
System.out.println(list);
// 獲取指定位置處的元素
System.out.println("第2個元素是（從0開始計數(shù)）：" + list.get(2));
// 返回元素索引
System.out.println("膜拜在的位置是：" + list.locate("膜拜"));
System.out.println("mobai所在的位置：" + list.locate("mobai"));
// 獲取長度
System.out.println("當(dāng)前線性表的長度：" + list.length());
// 判斷是否為空
System.out.println(list.isEmpty());
// 刪除最后一個元素
list.remove();
System.out.println("調(diào)用remove()后：" + list);
// 獲取長度
System.out.println("當(dāng)前線性表的長度：" + list.length());
// 刪除指定位置處元素
list.delete(3);
System.out.println("刪除第4個元素后：" + list);
// 獲取長度
System.out.println("當(dāng)前線性表的長度：" + list.length());
// 清空
list.clear();
System.out.println(list);
// 判斷是否為空
System.out.println(list.isEmpty());
}
}
五、鏈表相關(guān)的常用操作實(shí)現(xiàn)方法
/**
* 鏈表反轉(zhuǎn)
*
* @param head
* @return
*/
public Node ReverseIteratively(Node head) {
Node pReversedHead = head;
Node pNode = head;
Node pPrev = null;
while (pNode != null) {
Node pNext = pNode.next;
if (pNext == null) {
pReversedHead = pNode;
}
pNode.next = pPrev;
pPrev = pNode;
pNode = pNext;
}
this.head = pReversedHead;
return this.head;
}
采用快慢指針的方式查找單鏈表的中間節(jié)點(diǎn)，快指針一次走兩步，慢指針一次走一步，當(dāng)快指針走完時，慢指針剛好到達(dá)中間節(jié)點(diǎn)。
/**
* 查找單鏈表的中間節(jié)點(diǎn)
*
* @param head
* @return
*/
public Node SearchMid(Node head) {
Node p = this.head, q = this.head;
while (p != null && p.next != null && p.next.next != null) {
p = p.next.next;
q = q.next;
}
System.out.println("Mid:" + q.data);
return q;
}
采用兩個指針P1,P2，P1先前移K步，然后P1、P2同時移動，當(dāng)p1移動到尾部時，P2所指位置的元素即倒數(shù)第k個元素 。
/**
* 查找倒數(shù) 第k個元素
*
* @param head
* @param k
* @return
*/
public Node findElem(Node head, int k) {
if (k < 1 || k > this.length()) {
return null;
}
Node p1 = head;
Node p2 = head;
for (int i = 0; i < k; i++)// 前移k步
p1 = p1.next;
while (p1 != null) {
p1 = p1.next;
p2 = p2.next;
}
return p2;
}
/**
* 排序
*
* @return
*/
public Node orderList() {
Node nextNode = null;
int tmp = 0;
Node curNode = head;
while (curNode.next != null) {
nextNode = curNode.next;
while (nextNode != null) {
if (curNode.data > nextNode.data) {
tmp = curNode.data;
curNode.data = nextNode.data;
nextNode.data = tmp;
}
nextNode = nextNode.next;
}
curNode = curNode.next;
}
return head;
}
/**
* 刪除重復(fù)節(jié)點(diǎn)
*/
public void deleteDuplecate(Node head) {
Node p = head;
while (p != null) {
Node q = p;
while (q.next != null) {
if (p.data == q.next.data) {
q.next = q.next.next;
} else
q = q.next;
}
p = p.next;
}
}
/**
* 從尾到頭輸出單鏈表，采用遞歸方式實(shí)現(xiàn)
*
* @param pListHead
*/
public void printListReversely(Node pListHead) {
if (pListHead != null) {
printListReversely(pListHead.next);
System.out.println("printListReversely:" + pListHead.data);
}
}
/**
* 判斷鏈表是否有環(huán)，單向鏈表有環(huán)時，尾節(jié)點(diǎn)相同
*
* @param head
* @return
*/
public boolean IsLoop(Node head) {
Node fast = head, slow = head;
if (fast == null) {
return false;
}
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
System.out.println("該鏈表有環(huán)");
return true;
}
}
return !(fast == null || fast.next == null);
}
/**
* 找出鏈表環(huán)的入口
*
* @param head
* @return
*/
public Node FindLoopPort(Node head) {
Node fast = head, slow = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast)
break;
}
if (fast == null || fast.next == null)
return null;
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
https://www.cnblogs.com/ganch...
https://blog.csdn.net/jianyue...
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/71258.html
摘要：一般我們都構(gòu)造雙向循環(huán)鏈表。循環(huán)鏈表的操作和單鏈表的操作基本一致，差別僅僅在于算法中的循環(huán)條件有所不同。單向循環(huán)鏈表雙向循環(huán)鏈表單向循環(huán)鏈表是在單鏈表基礎(chǔ)上，將最后一個節(jié)點(diǎn)的指針指向鏈表頭。 維基百科 雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數(shù)據(jù)結(jié)點(diǎn)中都有兩個指針，分別指向直接后繼和直接前驅(qū)。所以，從雙向鏈表中的任意一個結(jié)點(diǎn)開始，都可以很方便地訪問它的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。一般我們都構(gòu)...
閱讀 2902·2023-04-26 02:14
閱讀 3751·2019-08-30 15:55
閱讀 1843·2019-08-29 16:42
閱讀 2757·2019-08-26 11:55
閱讀 2846·2019-08-23 13:38
閱讀 480·2019-08-23 12:10
閱讀 1308·2019-08-23 11:44
閱讀 2791·2019-08-23 11:43
