前言
上次講解了單向鏈表的原理《Java實(shí)現(xiàn)單向鏈表功能》，今天拓展一下實(shí)現(xiàn)鏈表的翻轉(zhuǎn)。
下面直接上代碼。
鏈表初始化
public class LinkedArray<T extends Number>{
//鏈表的頭節(jié)點(diǎn)
private Entry<T> head;
//節(jié)點(diǎn)實(shí)體類
static final class Entry<T>{
//記錄當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
Entry<T> next;
T t;
public Entry(T t) {
// TODO Auto-generated constructor stub
this.t = t;
}
}
}
添加節(jié)點(diǎn)
public void add(T t) {
//根據(jù)參數(shù)創(chuàng)建一個(gè)節(jié)點(diǎn)
Entry<T> entry = new Entry<T>(t);
//當(dāng)鏈表為空時(shí)，記錄head節(jié)點(diǎn)
if(head == null) {
head = entry;
}else {
//節(jié)點(diǎn)移動(dòng)，并且賦值，保持head節(jié)點(diǎn)為新增加的entry
entry.next = head;
head = entry;
}
}
添加的過程結(jié)合代碼注釋和下面圖片：
添加過程
鏈表反轉(zhuǎn)
public void reverse() {
///記錄current的節(jié)點(diǎn)是head大的下一個(gè)節(jié)點(diǎn)。
Entry<T> current = head.next;
//切斷head.next指向current，（當(dāng)前的head變?yōu)殒湵淼奈?，所以next為空）
head.next = null;
while(current != null) {
//記錄currentNext的節(jié)點(diǎn)是currentNext大的下一個(gè)節(jié)點(diǎn)。
Entry<T> currentNext = current.next;
//current.next反方向指向以前的節(jié)點(diǎn)
current.next = head;
//移動(dòng)head和current指針，到后面head重新成為頭節(jié)點(diǎn)
head = current;
current = currentNext;
}
}
翻轉(zhuǎn)的過程結(jié)合代碼注釋和下面圖片：
翻轉(zhuǎn)過程.png
整個(gè)鏈表的插入以及翻轉(zhuǎn)就實(shí)現(xiàn)了，但是要注意的是鏈表中元素的順序是按照插入的順序，并不是按照元素實(shí)際數(shù)值的大小排序。下面拓展實(shí)現(xiàn)插入按照排序。
自然數(shù)序插入
本文只討論Number類型的順序排列
public void addByOrder(T t) {
//根據(jù)參數(shù)創(chuàng)建一個(gè)節(jié)點(diǎn)
Entry<T> entry = new Entry<T>(t);
//當(dāng)鏈表為空時(shí)，記錄head節(jié)點(diǎn)
if(head == null) {
head = entry;
}else {
//從head開始，記錄上個(gè)節(jié)點(diǎn)，
//current是當(dāng)前節(jié)點(diǎn)，previous為current的上一個(gè)節(jié)點(diǎn)
Entry<T> current = head;
Entry<T> previous = head;
//遍歷整條鏈表，直到當(dāng)前current節(jié)點(diǎn)為空(鏈表已經(jīng)到尾部)
//或者插入的樹數(shù)值比當(dāng)前current大
while(current != null && t.doubleValue()>current.t.doubleValue()) {
//節(jié)點(diǎn)移動(dòng)
previous = current;
current = current.next;
}
//當(dāng)前鏈表只有head一個(gè)節(jié)點(diǎn)，
//并且傳入大的數(shù)值比head小(因?yàn)閏urrent == previous，current節(jié)點(diǎn)并沒有移動(dòng))
if(current == previous) {
entry.next = head;
head = entry;
}else {
//找到節(jié)點(diǎn)的位置，在previous和current的中間插入
previous.next = entry;
entry.next = current;
}
}
}
添加的過程結(jié)合代碼注釋和下面圖片：
自然順序插入.png
運(yùn)行結(jié)果
主函數(shù)隨機(jī)輸入10個(gè)數(shù)字,測(cè)試排序與不排序的情況。
public static void main(String[] args) {
// TODO Auto-generated method stub
add();
System.out.println("-------------分割線-----------");
addByOrder();
}
private static void add() {
LinkedArray<Number> list = new LinkedArray<>();
list.add(3);
list.add(4);
list.add(8);
list.add(6);
list.add(9);
list.add(2);
list.add(1);
list.add(5);
list.add(0);
list.add(7);
System.out.println(list.findAll());
list.reverse();
System.out.println(list.findAll());
}
private static void addByOrder() {
LinkedArray<Number> list = new LinkedArray<>();
list.addByOrder(3);
list.addByOrder(4);
list.addByOrder(8);
list.addByOrder(6);
list.addByOrder(9);
list.addByOrder(2);
list.addByOrder(1);
list.addByOrder(5);
list.addByOrder(0);
list.addByOrder(7);
System.out.println(list.findAll());
list.reverse();
System.out.println(list.findAll());
}
運(yùn)行結(jié)果
結(jié)果.png
總計(jì)
上面討論了插入節(jié)點(diǎn)，順序插入節(jié)點(diǎn)和翻轉(zhuǎn)的功能。鏈表需要重點(diǎn)理解清楚指針的移動(dòng)。更多的單向鏈表功能請(qǐng)參考《Java實(shí)現(xiàn)單向鏈表功能》
