很久之前用C語(yǔ)言實(shí)現(xiàn)過(guò)鏈表佃牛，現(xiàn)在已經(jīng)太久沒(méi)用C語(yǔ)言。就先用JAVA實(shí)現(xiàn)一個(gè)簡(jiǎn)單鏈表好了医舆，還是使用最原始的C語(yǔ)言實(shí)現(xiàn)的思路俘侠，想來(lái)語(yǔ)言變了實(shí)現(xiàn)方式大同小異吧。后續(xù)可能會(huì)不斷實(shí)現(xiàn)不一樣的數(shù)據(jù)結(jié)構(gòu)蔬将。
- 節(jié)點(diǎn)
先確定節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)（一個(gè)節(jié)點(diǎn)一個(gè)數(shù)字好了）爷速，后續(xù)慢慢一點(diǎn)點(diǎn)擴(kuò)展：
/**
* @author hsf
* @description
* @create 2018-07-14 下午3:47
**/
public class Node {
//數(shù)據(jù)
public int value;
//下一節(jié)點(diǎn)
public Node next;
}
或許我需要換一個(gè)習(xí)慣的寫(xiě)法;
/**
* @author hsf
* @description
* @create 2018-07-14 下午3:47
**/
public class Node {
//數(shù)據(jù)
private int value;
//下一節(jié)點(diǎn)
private Node next;
public int getValue() {
return value;
}
public Node setValue(int value) {
this.value = value;
return this;
}
public Node getNext() {
return next;
}
public Node setNext(Node next) {
this.next = next;
return this;
}
}
這個(gè)時(shí)候其實(shí)就可以創(chuàng)建一個(gè)鏈表了，直接創(chuàng)建main方法吧霞怀；
public static void main(String [] args){
//頭節(jié)點(diǎn)
Node head = new Node();
head.setValue(-1);
head.setNext(null);
//第一個(gè)節(jié)點(diǎn)
Node firstNode = new Node();
firstNode.setValue(0);
firstNode.setNext(null);
//鏈接
head.setNext(firstNode);
System.out.println(head.getValue() +
" " +head.getNext().getValue());
}
運(yùn)行結(jié)果
這可能是最簡(jiǎn)陋的鏈表了惫东。
繼續(xù)加工，把可以封裝的封裝起來(lái)毙石，能增加的增加廉沮。
給節(jié)添加構(gòu)造函數(shù)：
public Node(int value,Node next){
this.value =value;
this.next = next;
}
public Node(int value){
this.value = value;
}
public Node(){}
封裝幾個(gè)方法
public boolean hasNext(){
return this.next == null ? false : true;
}
public Node addToNext(Node node){
this.next = node;
return node;
}
改造main方法：
ublic static void main(String [] args){
//頭節(jié)點(diǎn)
Node head = new Node(-1);
//第一個(gè)節(jié)點(diǎn)
Node firstNode = new Node(0);
//第二個(gè)節(jié)點(diǎn)
Node secondNode = new Node(1);
//鏈接
head.addToNext(firstNode);
firstNode.addToNext(secondNode);
System.out.println(head.getValue() +
" " +head.getNext().getValue() +
" " +head.getNext().getNext().getValue());
}
說(shuō)實(shí)話這個(gè)輸出方式有些蠢，需要一個(gè)新的方式輸出徐矩，這里就寫(xiě)一個(gè)輸出方法滞时，效果就是以當(dāng)前節(jié)點(diǎn)為頭，輸出以后的所有節(jié)點(diǎn)滤灯。
繼續(xù)改造Node類
//直接重寫(xiě)toString好了
@Override
public String toString() {
String val = Integer.toString(value);
if(next != null){
val = val.concat(" hasNext ");
val = val.concat(next.toString());
}
return val;
}
這樣就直接可以輸出了坪稽，當(dāng)然也可以使用循環(huán)方法實(shí)現(xiàn)。原來(lái)的輸出直接換成
System.out.println(head);
輸出
這是有個(gè)問(wèn)題我假如需要加入一個(gè)節(jié)點(diǎn)到尾部怎么辦呢鳞骤，也就是也就是尾插法,新增一個(gè)方法：
//先找到尾巴窒百，在插入就好了 需要的話可以返回尾節(jié)點(diǎn)。
public void addToTail(Node node){
Node temp = this;
while(temp.hasNext()){
temp = temp.next;
}
temp.next = node;
}
既然有尾插法豫尽，那么就應(yīng)該來(lái)一個(gè)頭插法贝咙，頭插法一般需要一個(gè)頭節(jié)點(diǎn)，方法可以這么實(shí)現(xiàn)拂募。
//現(xiàn)將新節(jié)點(diǎn)的值指向原有頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)庭猩，再將頭節(jié)點(diǎn)指向新節(jié)點(diǎn)
public void addToHead(Node head,Node node){
node.next = head.next;
head.next = node;
}
當(dāng)我需要往指定的位置插入一個(gè)節(jié)點(diǎn)的時(shí)候就想到了之前寫(xiě)的一個(gè)方法addToNext，此時(shí)再詳細(xì)看這個(gè)方法會(huì)發(fā)現(xiàn)陈症，這里的這個(gè)方法有問(wèn)題蔼水，這里只是純粹的再在當(dāng)前節(jié)點(diǎn)后面添加，而不管這個(gè)節(jié)點(diǎn)之后是不是已經(jīng)有節(jié)點(diǎn)录肯。這樣的會(huì)造成鏈表被截?cái)嗯恳浮Ｐ薷脑蟹椒ǎ黾渔溄釉泄?jié)點(diǎn)到新節(jié)點(diǎn)论咏。
public Node addToNext(Node node){
node.next = this.next;
this.next = node;
return node;
}
最終main函數(shù)測(cè)試：
public static void main(String [] args){
//頭節(jié)點(diǎn)
Node head = new Node(-1);
//第一個(gè)節(jié)點(diǎn)
Node firstNode = new Node(0);
//第二個(gè)節(jié)點(diǎn)
Node secondNode = new Node(1);
//鏈接
head.addToNext(firstNode);
//加入第二個(gè)節(jié)點(diǎn)
firstNode.addToNext(secondNode);
//向尾部添加節(jié)點(diǎn)
head.addToTail(new Node(2));
//向頭部添加節(jié)點(diǎn)
head.addToHead(head,new Node(3));
//向中間添加節(jié)點(diǎn)
secondNode.addToNext(new Node(4));
//輸出
System.out.println(head);
}
最終輸出：
以上是一個(gè)單項(xiàng)鏈表簡(jiǎn)單實(shí)現(xiàn)优炬；
-
單向鏈表逆轉(zhuǎn)
假設(shè)只知道一個(gè)頭節(jié)點(diǎn)。難度其實(shí)在于單向鏈表在沒(méi)有指向前趨節(jié)點(diǎn)的情況下怎么獲取到前驅(qū)節(jié)點(diǎn)厅贪，并且逆轉(zhuǎn)之后怎么獲取正確的原有下一節(jié)點(diǎn)蠢护。
先創(chuàng)建一個(gè)測(cè)試的方法入口并且定義好測(cè)試用的鏈表。public static void main(String[] args) { //1個(gè) Node head = new Node(1); System.out.println(head); System.out.println(reverse(head)); //2個(gè) head = new Node(1); head.addToNext(new Node(2)); System.out.println(head); System.out.println(reverse(head)); //3個(gè) head = new Node(1); head.addToNext(new Node(2)) .addToNext(new Node(3)); System.out.println(head); System.out.println(reverse(head)); //4個(gè) head = new Node(1); head.addToNext(new Node(2)) .addToNext(new Node(3)) .addToNext(new Node(4)); System.out.println(head); System.out.println(reverse(head)); //多個(gè) head = new Node(1); Node tempHead = head; for (int i = 2; i <= 15; i++) { head = head.addToNext(new Node(i)); } System.out.println(tempHead); System.out.println(reverse(tempHead)); }·直接在原基礎(chǔ)鏈表上反轉(zhuǎn)
操作：遍歷原有鏈表养涮，直接將其下一個(gè)節(jié)點(diǎn)引用反轉(zhuǎn)public static Node reverse(Node head) { Node curNode = null; Node afterNode = null; if (head == null) { return null; } if (head.hasNext()) { curNode = head.getNext(); } else { return head; //假如只有一個(gè)節(jié)點(diǎn)葵硕，則不反轉(zhuǎn) } if (curNode.hasNext()) { afterNode = curNode.getNext(); } else { curNode.setNext(head); //假如鏈表只有兩個(gè)節(jié)點(diǎn) 直接反轉(zhuǎn)引用 head.setNext(null); return curNode; } //假如有3個(gè)及3個(gè)以上 //先將第一個(gè)節(jié)點(diǎn)獨(dú)立，如果不獨(dú)立則這個(gè)節(jié)點(diǎn)將永遠(yuǎn)指向原鏈表中的第二個(gè)節(jié)點(diǎn)贯吓，則會(huì)成環(huán)懈凹。必須切斷引用。 head.setNext(null); Node newHead = head;//作為尾節(jié)點(diǎn) while (afterNode.hasNext()) { curNode.setNext(newHead); newHead = curNode; curNode = afterNode; afterNode = afterNode.getNext(); } curNode.setNext(newHead); afterNode.setNext(curNode); return afterNode; }
執(zhí)行結(jié)果：
方法還有別的并且這個(gè)方法也應(yīng)該是可以簡(jiǎn)化的,這個(gè)只是第一感覺(jué)寫(xiě)出來(lái)的悄谐，后續(xù)再更新......未完......
