Java怎樣實現(xiàn)鏈表

小編給大家分享一下Java怎樣實現(xiàn)鏈表，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

創(chuàng)新互聯(lián)提供高防主機、云服務(wù)器、香港服務(wù)器、成都服務(wù)器托管等

鏈表分為單鏈表,雙向鏈表和循環(huán)鏈表,是一種鏈?zhǔn)酱鎯Y(jié)構(gòu),由一個個結(jié)點鏈?zhǔn)綐?gòu)成,結(jié)點包含數(shù)據(jù)域和指針域,其中單鏈表是只有一個指向后驅(qū)結(jié)點的指針,雙向鏈表除頭結(jié)點和尾結(jié)點外,每個結(jié)點都有一個前驅(qū)指針和一個后繼指針,循環(huán)鏈表的尾結(jié)點的指針指向頭結(jié)點.

相比數(shù)組而言,鏈表的插入和刪除比較快,查詢慢.

本文主要以單鏈表為例,介紹下鏈表的常用算法操作.

單鏈表的結(jié)構(gòu):

在java語言中,鏈表的每個結(jié)點用Node類來表示:

package com.linkedlist;public class Node {  private int data;// 結(jié)點數(shù)據(jù)  private Node next;// 下一個結(jié)點  public Node(int data) {    this.data = data;  }  public int getData() {    return data;  }  public void setData(int data) {    this.data = data;  }  public Node getNext() {    return next;  }  public void setNext(Node next) {    this.next = next;  }}

定義一個鏈表操作類,里面包含常用的操作:

package com.linkedlist;import java.util.Hashtable;public class LinkedListOperator {  private Node head = null;// 頭結(jié)點  // 在鏈表的末尾增加一個結(jié)點  private void addNode(int data) {    Node newNode = new Node(data);    if (head == null) {      head = newNode;      return;    }    Node temp = head;    while (temp.getNext() != null) {      temp = temp.getNext();    }    temp.setNext(newNode);  }  // 打印鏈表結(jié)點  private void printLink() {    Node curNode = head;    while (curNode != null) {      System.out.println(curNode.getData());      curNode = curNode.getNext();    }    System.out.println("===========");  }  // 求鏈表長度  private int getLength() {    int len = 0;    Node curNode = head;    while (curNode != null) {      len++;      curNode = curNode.getNext();    }    return len;  }  // 刪除某一個結(jié)點  private boolean delNode(int index) {    if (index < 1) {      return false;    }    if (index == 1) {      head = head.getNext();      return true;    }    Node preNode = head;    Node curNode = head.getNext();    int n = 1;    while (curNode.getNext() != null) {      if (n == index) {        preNode.setData(curNode.getData());        preNode.setNext(curNode.getNext());        return true;      }      preNode = preNode.getNext();      curNode = curNode.getNext();      n++;    }    if (curNode.getNext() == null) {      preNode.setNext(null);    }    return false;  }  // 鏈表排序:選擇排序法,從小到大  private void sortList() {    Node curNode = head;    while (curNode != null) {      Node nextNode = curNode.getNext();      while (nextNode != null) {        if (curNode.getData() > nextNode.getData()) {          int temp = curNode.getData();          curNode.setData(nextNode.getData());          nextNode.setData(temp);        }        nextNode = nextNode.getNext();      }      curNode = curNode.getNext();    }  }  // 去掉重復(fù)元素  private void distinctLink() {    Hashtable<Integer, Integer> map = new Hashtable<Integer, Integer>();    Node curNode = head;    Node preNode = null;    while (curNode != null) {      if (map.containsKey(curNode.getData())) {        preNode.setData(curNode.getData());        preNode.setNext(curNode.getNext());      } else {        map.put(curNode.getData(), 1);        preNode = curNode;      }      curNode = curNode.getNext();    }  }  // 返回倒數(shù)第k個結(jié)點,定義兩個指針,第一個指針向前移動K-1次,之后兩個指針同時前進,  // 當(dāng)?shù)谝粋€指針到達末尾時,第二個指針?biāo)诘奈恢眉礊榈箶?shù)第k個結(jié)點  private Node getReverNode(int k) {    if (k < 1) {      return null;    }    Node first = head;    Node second = head;    for (int i = 0; i < k - 1; i++) {      first = first.getNext();    }    while (first.getNext() != null) {      first = first.getNext();      second = second.getNext();    }    return second;  }  // 反轉(zhuǎn)鏈表  private void reserveLink() {    Node preNode = null;    Node curNode = head;    Node tempNode = null;    while (curNode != null) {      tempNode = curNode.getNext();      curNode.setNext(preNode);      preNode = curNode;      curNode = tempNode;    }    head = preNode;  }  // 尋找鏈表的中間結(jié)點  private Node getMiddleNode() {    Node slowNode = head;    Node quickNode = head;    while (slowNode.getNext() != null && quickNode.getNext() != null) {      slowNode = slowNode.getNext();      quickNode = quickNode.getNext().getNext();    }    return slowNode;  }  // 判斷鏈表是否有環(huán)  private boolean isRinged() {    if (head == null) {      return false;    }    Node slowNode = head;    Node quickNode = head;    while (slowNode.getNext() != null && quickNode.getNext() != null) {      slowNode = slowNode.getNext();      quickNode = quickNode.getNext().getNext();      if (slowNode.getData() == quickNode.getData()) {        return true;      }    }    return false;  }  // 刪除指定結(jié)點  private boolean delNode(Node node) {    if (node.getNext() == null) {      return false;// 在不知道頭結(jié)點的情況下,沒法刪除單鏈表的尾結(jié)點    }    node.setData(node.getNext().getData());    node.setNext(node.getNext().getNext());    return true;  }  // 判斷兩個鏈表是否相交:相交的鏈表的尾結(jié)點相同  private boolean isCross(Node n1, Node n2) {    while (n1.getNext() != null) {      n1 = n1.getNext();    }    while (n2.getNext() != null) {      n2 = n2.getNext();    }    if (n1.getData() == n2.getData()) {      return true;    }    return false;  }  // 求相交鏈表的起始點  private Node getFirstCrossNode(LinkedListOperator l1, LinkedListOperator l2) {    int len = l1.getLength() - l2.getLength();    Node n1 = l1.head;    Node n2 = l2.head;    if (len > 0) {      for (int i = 0; i < len; i++) {        n1 = n1.getNext();      }    } else {      for (int i = 0; i < len; i++) {        n2 = n2.getNext();      }    }    while (n1.getData() != n2.getData()) {      n1 = n1.getNext();      n2 = n2.getNext();    }    return n1;  }  public static void main(String[] args) {    LinkedListOperator llo = new LinkedListOperator();    llo.addNode(10);    llo.addNode(4);    llo.addNode(6);    llo.addNode(8);    llo.printLink();    // llo.delNode(4);    // llo.sortList();    // llo.distinctLink();    // System.out.println(llo.getReverNode(3).getData());    // llo.reserveLink();    // System.out.println(llo.getMiddleNode().getData());    // System.out.println(llo.isRinged());    llo.delNode(llo.head.getNext().getNext());    llo.printLink();  }}

以上是“Java怎樣實現(xiàn)鏈表”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對大家有所幫助，如果還想學(xué)習(xí)更多知識，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道！

網(wǎng)站題目：Java怎樣實現(xiàn)鏈表
網(wǎng)頁鏈接：http://muchs.cn/article38/jojesp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供移動網(wǎng)站建設(shè)、企業(yè)網(wǎng)站制作、網(wǎng)站排名、用戶體驗、網(wǎng)站營銷、虛擬主機

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)