java链表实现_数据结构——基于java的链表实现（真正理解链表这种数据结构）...
一、鏈表介紹
1、什么是鏈表？
鏈表是一種物理存儲(chǔ)結(jié)構(gòu)上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。如下圖所示，在數(shù)據(jù)結(jié)構(gòu)中，a1里面的指針存儲(chǔ)著a2的地址，這樣一個(gè)鏈接一個(gè)，就形成了鏈表。
相鄰元素之間通過指針鏈接
最后一個(gè)元素的后繼指針為NULL
在程序執(zhí)行過程中，鏈表的長(zhǎng)度可以增加或縮小
鏈表的空間能夠按需分配
沒有內(nèi)存空間的浪費(fèi)
2、鏈表的優(yōu)缺點(diǎn)？
優(yōu)點(diǎn)：
插入和刪除時(shí)不需移動(dòng)其他元素, 只需改變指針,效率高。
鏈表各個(gè)節(jié)點(diǎn)在內(nèi)存中空間不要求連續(xù)，空間利用率高。
大小沒有固定，拓展很靈活。
缺點(diǎn)：
查找數(shù)據(jù)時(shí)效率低，因?yàn)椴痪哂须S機(jī)訪問性。
3、鏈表的種類？
有單鏈表、雙向鏈表、循環(huán)單鏈表、循環(huán)雙鏈表等等。
二、單鏈的實(shí)現(xiàn)和相關(guān)操作
1、鏈表類的創(chuàng)建(以下均已單鏈表為基準(zhǔn))
public class SingleLinkedList {
//head為頭節(jié)點(diǎn)，他不存放任何的數(shù)據(jù)，只是充當(dāng)一個(gè)指向鏈表中真正存放數(shù)據(jù)的第一個(gè)節(jié)點(diǎn)的作用
public Node head = new Node();
//內(nèi)部類,定義node節(jié)點(diǎn),使用內(nèi)部類的最大好處是可以和外部類進(jìn)行私有操作的互相訪問
class Node{
public int val; //int類型會(huì)導(dǎo)致head節(jié)點(diǎn)的val為0，不影響我們學(xué)習(xí)
public Node next;
public Node(){}
public Node(int val){
this.val = val;
}
}
//下面就可以自定義各種鏈表操作。。。
}
2、鏈表添加結(jié)點(diǎn)
//找到鏈表的末尾結(jié)點(diǎn)，把新添加的數(shù)據(jù)作為末尾結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)
public void add(int data){
if (head.next == null){
head.next = new Node(data);
return;
}
Node temp = head;
while (temp.next != null){
temp = temp.next;
}
temp.next = new Node(data);
}
3、鏈表刪除節(jié)點(diǎn)
//把要?jiǎng)h除結(jié)點(diǎn)的前結(jié)點(diǎn)指向要?jiǎng)h除結(jié)點(diǎn)的后結(jié)點(diǎn)，即直接跳過待刪除結(jié)點(diǎn)
public boolean deleteNode(int index){
if (index < 0 || index > length() ){
return false;
}
if (index == 1){ //刪除頭結(jié)點(diǎn)
head = head.next;
return true;
}
Node preNode = head;
Node curNode = preNode.next;
int i = 2;
while (curNode!=null){
if (index == i){
preNode.next = curNode.next; //指向刪除節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)
break;
}
preNode = curNode;
curNode = preNode.next;
i++;
}
return true;
}
4、鏈表長(zhǎng)度、節(jié)點(diǎn)獲取以及鏈表遍歷
//獲取鏈表長(zhǎng)度
public int length(){
int length = 0;
Node temp = head;
while (temp.next!=null){
length++;
temp = temp.next;
}
return length;
}
//獲取最后一個(gè)節(jié)點(diǎn)
public Node getLastNode(){
Node temp = head;
while (temp.next != null){
temp = temp.next;
}
return temp;
}
//獲取第index節(jié)點(diǎn)
public Node getNodeByIndex(int index){
if(index<1 || index>length()){
return null;
}
Node temp = head;
int i = 1;
while (temp.next != null){
temp = temp.next;
if (index==i){
break;
}
i++;
}
return temp;
}
//打印節(jié)點(diǎn)
public void printLink(){
Node curNode = head;
while(curNode !=null){
System.out.print(curNode.val+" ");
curNode = curNode.next;
}
}
5、查找單鏈表中的倒數(shù)第n個(gè)結(jié)點(diǎn)
//兩個(gè)指針，第一個(gè)指針向前移動(dòng)k-1次，之后兩個(gè)指針共同前進(jìn)，當(dāng)前面的指針到達(dá)末尾時(shí)，后面的指針?biāo)诘奈恢镁褪堑箶?shù)第k個(gè)位置
public Node findReverNode(int index){
if(index<1 || index>length()){
return null;
}
Node first = head;
Node second = head;
for (int i = 0; i < index - 1; i++) {
second = second.next;
}
while (second.next != null){
first = first.next;
second = second.next;
}
return first;
}
6、查找單鏈表中的中間結(jié)點(diǎn)
//也是設(shè)置兩個(gè)指針first和second，只不過這里是，兩個(gè)指針同時(shí)向前走，second指針每次走兩步，
//first指針每次走一步，直到second指針走到最后一個(gè)結(jié)點(diǎn)時(shí)，此時(shí)first指針?biāo)傅慕Y(jié)點(diǎn)就是中間結(jié)點(diǎn)。
public Node findMiddleNode(){
Node slowPoint = head;
Node quickPoint = head;
//鏈表結(jié)點(diǎn)個(gè)數(shù)為奇數(shù)時(shí),返回的是中間結(jié)點(diǎn)；鏈表結(jié)點(diǎn)個(gè)數(shù)為偶數(shù)時(shí)，返回的是中間兩個(gè)結(jié)點(diǎn)中的前個(gè)
while(quickPoint != null && quickPoint.next != null){
slowPoint = slowPoint.next;
quickPoint = quickPoint.next.next;
}
return slowPoint;
}
7、從尾到頭打印單鏈表
//方法一：先反轉(zhuǎn)鏈表，再輸出鏈表，需要鏈表遍歷兩次(不建議這么做,改變了鏈表的結(jié)構(gòu))
。。。
//方法二、通過遞歸來實(shí)現(xiàn)(鏈表很長(zhǎng)的時(shí)候，就會(huì)導(dǎo)致方法調(diào)用的層級(jí)很深，有可能造成StackOverflowError)
public void reservePrt(Node node){
if(node != null){
reservePrt(node.next);
System.out.print(node.val+" ");
}
}
//方法三、把鏈表中的元素放入棧中再輸出，需要維護(hù)額外的棧空間
public void reservePrt2(Node node){
if(node != null){
Stack stack = new Stack(); //新建一個(gè)棧
Node current = head;
//將鏈表的所有結(jié)點(diǎn)壓棧
while (current != null) {
stack.push(current); //將當(dāng)前結(jié)點(diǎn)壓棧
current = current.next;
}
//將棧中的結(jié)點(diǎn)打印輸出即可
while (stack.size() > 0) {
System.out.print(stack.pop().val+" "); //出棧操作
}
}
}
8、單鏈表的反轉(zhuǎn)(1->2->3->4變?yōu)?->3->2->1)
//從頭到尾遍歷原鏈表，每遍歷一個(gè)結(jié)點(diǎn)，將其摘下放在新鏈表的最前端。注意鏈表為空和只有一個(gè)結(jié)點(diǎn)的情況。時(shí)間復(fù)雜度為O(n)
public void reserveLink(){
Node curNode = head;
Node preNode = null;
while (curNode.next != null){
Node nextNode = curNode.next;
//主要理解以下邏輯
curNode.next = preNode; //將current的下一個(gè)結(jié)點(diǎn)指向新鏈表的頭結(jié)點(diǎn)
preNode = curNode; //將改變了指向的cruNode賦值給preNode
curNode = nextNode;
}
curNode.next = preNode;
preNode = curNode;
head = preNode;
}
9、判斷鏈表是否有環(huán)
//設(shè)置快指針和慢指針，慢指針每次走一步，快指針每次走兩步,當(dāng)快指針與慢指針相等時(shí)，就說明該鏈表有環(huán)
public boolean isRinged(){
if(head == null){
return false;
}
Node slow = head;
Node fast = head;
while(fast.next != null && fast.next.next != null){
slow = slow.next;
fast = fast.next.next;
if(fast == slow){
return true;
}
}
return false;
}
10、取出有環(huán)鏈表中，環(huán)的長(zhǎng)度
//獲取環(huán)的相遇點(diǎn)
public Node getFirstMeet(){
if(head == null){
return null;
}
Node slow = head;
Node fast = head;
while(fast.next != null && fast.next.next != null){
slow = slow.next;
fast = fast.next.next;
if(fast == slow){
return slow;
}
}
return null;
}
//首先得到相遇的結(jié)點(diǎn)，這個(gè)結(jié)點(diǎn)肯定是在環(huán)里，我們可以讓這個(gè)結(jié)點(diǎn)對(duì)應(yīng)的指針一直往下走，直到它回到原點(diǎn)，就可以算出環(huán)的長(zhǎng)度
public int getCycleLength(){
Node current = getFirstMeet(); //獲取相遇點(diǎn)
int length = 0;
while (current != null) {
current = current.next;
length++;
if (current == getFirstMeet()) { //當(dāng)current結(jié)點(diǎn)走到原點(diǎn)的時(shí)候
return length;
}
}
return length;
}
11、判斷兩個(gè)鏈表是否相交
//兩個(gè)鏈表相交，則它們的尾結(jié)點(diǎn)一定相同，比較兩個(gè)鏈表的尾結(jié)點(diǎn)是否相同即可
public boolean isCross(Node head1, Node head2){
Node temp1 = head1;
Node temp2 = head2;
while(temp1.next != null){
temp1 = temp1.next;
}
while(temp2.next != null){
temp2 = temp2.next;
}
if(temp1 == temp2){
return true;
}
return false;
}
12、如果鏈表相交，求鏈表相交的起始點(diǎn)
/**
* 如果鏈表相交，求鏈表相交的起始點(diǎn)：
* 1、首先判斷鏈表是否相交，如果兩個(gè)鏈表不相交，則求相交起點(diǎn)沒有意義
* 2、求出兩個(gè)鏈表長(zhǎng)度之差：len=length1-length2
* 3、讓較長(zhǎng)的鏈表先走len步
* 4、然后兩個(gè)鏈表同步向前移動(dòng)，每移動(dòng)一次就比較它們的結(jié)點(diǎn)是否相等，第一個(gè)相等的結(jié)點(diǎn)即為它們的第一個(gè)相交點(diǎn)
*/
public Node findFirstCrossPoint(SingleLinkedList linkedList1, SingleLinkedList linkedList2){
//鏈表不相交
if(!isCross(linkedList1.head,linkedList2.head)){
return null;
}else{
int length1 = linkedList1.length();//鏈表1的長(zhǎng)度
int length2 = linkedList2.length();//鏈表2的長(zhǎng)度
Node temp1 = linkedList1.head;//鏈表1的頭結(jié)點(diǎn)
Node temp2 = linkedList2.head;//鏈表2的頭結(jié)點(diǎn)
int len = length1 - length2;//鏈表1和鏈表2的長(zhǎng)度差
if(len > 0){//鏈表1比鏈表2長(zhǎng)，鏈表1先前移len步
for(int i=0; i
temp1 = temp1.next;
}
}else{//鏈表2比鏈表1長(zhǎng)，鏈表2先前移len步
for(int i=0; i
temp2 = temp2.next;
}
}
//鏈表1和鏈表2同時(shí)前移,直到找到鏈表1和鏈表2相交的結(jié)點(diǎn)
while(temp1 != temp2){
temp1 = temp1.next;
temp2 = temp2.next;
}
return temp1;
}
}
13、合并兩個(gè)有序的單鏈表(將1->2->3和1->3->4合并為1->1->2->3->3->4)
//兩個(gè)參數(shù)代表的是兩個(gè)鏈表的頭結(jié)點(diǎn)
//方法一
public Node mergeLinkList(Node head1, Node head2) {
if (head1 == null && head2 == null) { //如果兩個(gè)鏈表都為空
return null;
}
if (head1 == null) {
return head2;
}
if (head2 == null) {
return head1;
}
Node head; //新鏈表的頭結(jié)點(diǎn)
Node current; //current結(jié)點(diǎn)指向新鏈表
// 一開始，我們讓current結(jié)點(diǎn)指向head1和head2中較小的數(shù)據(jù)，得到head結(jié)點(diǎn)
if (head1.val <= head2.val) {
head = head1;
current = head1;
head1 = head1.next;
} else {
head = head2;
current = head2;
head2 = head2.next;
}
while (head1 != null && head2 != null) {
if (head1.val <= head2.val) {
current.next = head1; //新鏈表中，current指針的下一個(gè)結(jié)點(diǎn)對(duì)應(yīng)較小的那個(gè)數(shù)據(jù)
current = current.next; //current指針下移
head1 = head1.next;
} else {
current.next = head2;
current = current.next;
head2 = head2.next;
}
}
//合并剩余的元素
if (head1 != null) { //說明鏈表2遍歷完了，是空的
current.next = head1;
}
if (head2 != null) { //說明鏈表1遍歷完了，是空的
current.next = head2;
}
return head;
}
//方法二：遞歸法
public Node merge(Node head1, Node head2) {
if(head1 == null){
return head2;
}
if(head2 == null){
return head1;
}
Node head = null;
if(head1.val <= head2.val){
head = head1;
head.next = merge(head1.next,head2);
}else{
head = head2;
head.next = merge(head1,head2.next);
}
return head;
}
到此單鏈表的一些常見操作展示的差不多了,如有興趣可繼續(xù)深入研究~~~
三、其它種類鏈表(拓展)
1、雙向鏈表(java.util中的LinkedList就是雙鏈的一種實(shí)現(xiàn))
雙向鏈表(雙鏈表)是鏈表的一種。和單鏈表一樣，雙鏈表也是由節(jié)點(diǎn)組成，它的每個(gè)數(shù)據(jù)結(jié)點(diǎn)中都有兩個(gè)指針，分別指向直接后繼和直接前驅(qū)。所以，從雙向鏈表中的任意一個(gè)結(jié)點(diǎn)開始，都可以很方便地訪問它的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。一般我們都構(gòu)造雙向循環(huán)鏈表。
優(yōu)點(diǎn)：對(duì)于鏈表中一個(gè)給的的結(jié)點(diǎn)，可以從兩個(gè)方向進(jìn)行操，雙向鏈表相對(duì)單鏈表更適合元素的查詢工作。
缺點(diǎn)：
每個(gè)結(jié)點(diǎn)需要再添加一個(gè)額外的指針，因此需要更多的空間開銷。
結(jié)點(diǎn)的插入或者刪除更加費(fèi)時(shí)。
以下是雙鏈的相關(guān)實(shí)現(xiàn)和操作(其實(shí)單鏈弄明白了，雙鏈只不過多維護(hù)了個(gè)前節(jié)點(diǎn))
public class DoubleLink {
// 表頭
private DNode mHead;
// 節(jié)點(diǎn)個(gè)數(shù)
private int mCount;
// 雙向鏈表“節(jié)點(diǎn)”對(duì)應(yīng)的結(jié)構(gòu)體
private class DNode {
public DNode prev;
public DNode next;
public T value;
public DNode(T value, DNode prev, DNode next) {
this.value = value;
this.prev = prev;
this.next = next;
}
}
// 構(gòu)造函數(shù)
public DoubleLink() {
// 創(chuàng)建“表頭”。注意：表頭沒有存儲(chǔ)數(shù)據(jù)！
mHead = new DNode(null, null, null);
mHead.prev = mHead.next = mHead;
// 初始化“節(jié)點(diǎn)個(gè)數(shù)”為0
mCount = 0;
}
// 返回節(jié)點(diǎn)數(shù)目
public int size() {
return mCount;
}
// 返回鏈表是否為空
public boolean isEmpty() {
return mCount==0;
}
// 獲取第index位置的節(jié)點(diǎn)
private DNode getNode(int index) {
if (index<0 || index>=mCount)
throw new IndexOutOfBoundsException();
// 正向查找
if (index <= mCount/2) {
DNode node = mHead.next;
for (int i=0; i
node = node.next;
return node;
}
// 反向查找
DNode rnode = mHead.prev;
int rindex = mCount - index -1;
for (int j=0; j
rnode = rnode.prev;
return rnode;
}
// 獲取第index位置的節(jié)點(diǎn)的值
public T get(int index) {
return getNode(index).value;
}
// 獲取第1個(gè)節(jié)點(diǎn)的值
public T getFirst() {
return getNode(0).value;
}
// 獲取最后一個(gè)節(jié)點(diǎn)的值
public T getLast() {
return getNode(mCount-1).value;
}
// 將節(jié)點(diǎn)插入到第index位置之前
public void insert(int index, T t) {
if (index==0) {
DNode node = new DNode(t, mHead, mHead.next);
mHead.next.prev = node;
mHead.next = node;
mCount++;
return ;
}
DNode inode = getNode(index);
DNode tnode = new DNode(t, inode.prev, inode);
inode.prev.next = tnode;
inode.next = tnode;
mCount++;
return ;
}
// 將節(jié)點(diǎn)插入第一個(gè)節(jié)點(diǎn)處。
public void insertFirst(T t) {
insert(0, t);
}
// 將節(jié)點(diǎn)追加到鏈表的末尾
public void appendLast(T t) {
DNode node = new DNode(t, mHead.prev, mHead);
mHead.prev.next = node;
mHead.prev = node;
mCount++;
}
// 刪除index位置的節(jié)點(diǎn)
public void del(int index) {
DNode inode = getNode(index);
inode.prev.next = inode.next;
inode.next.prev = inode.prev;
inode = null;
mCount--;
}
// 刪除第一個(gè)節(jié)點(diǎn)
public void deleteFirst() {
del(0);
}
// 刪除最后一個(gè)節(jié)點(diǎn)
public void deleteLast() {
del(mCount-1);
}
}
2、循環(huán)單鏈表、循環(huán)雙鏈表(操作和單鏈、雙鏈?zhǔn)且粯拥?#xff0c;不贅述了)
四、總結(jié)
本文主要是對(duì)于鏈表這種數(shù)據(jù)結(jié)構(gòu)的介紹和認(rèn)知，明白鏈表的優(yōu)劣勢(shì)。
重點(diǎn)是要學(xué)會(huì)對(duì)于單鏈的操作，體會(huì)它的一些獨(dú)到之處，至于其它衍生鏈表，舉一反三而已！！！
個(gè)人博客地址：
總結(jié)
以上是生活随笔為你收集整理的java链表实现_数据结构——基于java的链表实现（真正理解链表这种数据结构）...的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： python读取大文件的某行_Pytho
- 下一篇： 硬盘维修手记之"报废"硬盘维修实录