本文目錄一覽：
用Java語言實現單向鏈表
1.先定義一個節點類
package com.buren;
public class IntNode {
//定義一個節點類
int
info;
//定義屬性，節點中的值
IntNode next;
//定義指向下一個節點的屬性
public IntNode(int
i){ //構造一個next為空的節點
this(i,null);
}
public IntNode(int i,IntNode
n){ //構造值為i指向n的節點
info=i;
next=n;
}
}
2.再定義一個鏈表類，這是主要部分
package com.buren;
public class IntSLList {
private IntNode head,tail;
//定義指向頭結點和尾結點的指針，
//如果大家看着這個不像指針的話，那就需要對指針有更深刻的了解
public
IntSLList(){
//定義一個空節點
head=tail=null;
}
public boolean
isEmpty(){
//判斷節點是否為空
return
head==null;
//這行代碼看起來似乎很神奇，其實真的很神奇，偶是服了
}
public void addToHead(int el){
//將el插入到頭結點前
head=new
IntNode(el,head);
//將節點插入到頭結點前，作為新的投節點
if(head==tail){
//給空鏈表插入節點時
tail=head;
//頭結點和尾結點指向同一個節點
}
}
public void addToTail(int
el){
//向鏈表的尾部增加結點
if(!isEmpty()){
//判斷鏈表是否為空
tail.next=new
IntNode(el);
//新建立一個值為el的節點，將鏈表的尾結點指向新節點
tail=tail.next;
//更新尾指針的指向
}else{
head=tail=new
IntNode(el);
//如果鏈表為空，新建立一個節點，將頭尾指針同時指向這個節點
}
}
public int
deleteFromHead(){
//刪除頭結點，將節點信息返回
int
el=head.info;
//取出節點信息
if(head==tail){
//如果鏈表中只有一個節點
head=tail=null;
//刪除這一個節點
}else{
head=head.next;
//如果鏈表中不止一個節點，將頭結點的下一個節點作為頭結點
}
return
el;
//返回原頭結點的值
}
public int
deleteFromTail(){
//刪除尾結點，返回尾結點的信息
int
el=tail.info;
//取出尾結點的值
if(head==tail){
// 如果鏈表中只有一個節點
head=tail=null;
//刪除這個節點
}else{
IntNode
temp;
//定義中間變量
for(temp=head;temp.next!=tail;temp=temp.next);
//找出尾結點的前一個節點，注意最後的分號，
//這個for循環是沒有循環體的，目的在於找出尾結點的前一個節點
//在整個程序中用了很多次這樣的寫法，相當經典啊
tail=temp;
//將找出來的節點作為尾結點，刪除原來的尾結點
tail.next=null;
//將新尾結點的指向設為空
}
return
el;
//返回原尾結點的信息
}
public void
printAll(){
//打印鏈表中所有節點的信息
if(isEmpty()){
//如果鏈表為空
System.out.println(“This
list is
empty!”);
//輸出提示信息
return;
//返回到調用的地方
}
if(head==tail){
//當鏈表中只有一個節點時
System.out.println(head.info);
//輸出這個節點的信息，就是頭結點的信息
return;
}
IntNode
temp;
//定義一個中間變量
for(temp=head;temp!=null;temp=temp.next){
//遍歷整個鏈表
System.out.print(temp.info+”
“);
//輸出每個節點的信息
}
System.out.println();
//輸出一個換行，可以沒有這一行
}
public boolean isInList(int
el){
//判斷el是否存在於鏈表中
IntNode
temp;
//定義一個中間變量
for(temp=head;temp!=null
temp.info!=el;temp=temp.next);
//將el找出來，注意最後的分
return
temp!=null;
// 如果存在返回true，否則返回flase，這兩行代碼很有思想
}
public void delete(int
el){
//刪除鏈表中值為el的節點
if(head.info==el
head==tail){
//如果只有一個節點，並且節點的值為el
head=tail=null;
//刪除這個節點
}else
if(head.info==el){
// 不止一個節點，而頭結點的值就是el
head=head.next;
//刪除頭結點
}else{
IntNode
pred,temp;
//定義兩個中間變量
for(pred=head,temp=head.next;temp.info!=el
temp.next!=null;pred=pred.next,temp=temp.next);
//跟上面的類似，自己琢磨吧，也是要注意最後的分號
pred.next=temp.next;
//將temp指向的節點刪除，最好畫一個鏈表的圖，有助於理解
if(temp==tail){
//如果temp指向的節點是尾結點
tail=pred;
//將pred指向的節點設為尾結點，
}
}
}
//下面這個方法是在鏈表中值為el1的節點前面插入一個值為el2的節點，
//用類似的思想可以再寫一個在鏈表中值為el1的節點後面插入一個值為el2的節點
public boolean insertToList(int el1,int
el2){
//定義一個插入節點的方法，插入成功返回true，否則返回false
IntNode
pred,temp; //定義兩個中間變量
if(isEmpty()){
//判斷鏈表是否為空
return
false;
//如果鏈表為空就直接返回false
}
if(head.info==el1
head==tail){
//如果鏈表中只有一個節點，並且這個節點的值是el1
head=new
IntNode(el2,head);
//新建立一個節點
return
true;
}else if(head.info==el1){
IntNode t=new
IntNode(el2);
t.next=head;
head=t;
return
true;
}else{
for(pred=head,temp=head.next;temp!=null
temp.info!=el1;pred=pred.next,temp=temp.next);
if(temp!=null){
IntNode
a=new IntNode(el2);
pred.next=a;
a.next=temp;
return
true;
}else{
System.out.println(el1+”
NOT EXEISTS!”);
return
false;
}
}
}
3.下面是測試代碼
public static void main(String[] args){
IntSLList test=new
IntSLList();
//test.addToHead(7);
test.addToTail(7);
System.out.println(test.insertToList(7,5));
test.printAll();
System.out.println(test.isInList(123));
}
}
在Java中如何實現雙向鏈表
雙向鏈表：就是有雙向指針，即雙向的鏈域。
鏈結點的結構：
┌────┬────┬────────┐
│ data │ next │ previous │
└────┴────┴────────┘
雙向鏈表不必是雙端鏈表(持有對最後一個鏈結點的引用)，雙端鏈表插入時是雙向的。
有兩條鏈：一條從頭到尾，一條從尾到頭，刪除遍歷時也是雙向的。
/**
* 雙向鏈表
*/
public class DoublyLinkedListt {
private Linkt head; //首結點
private Linkt rear; //尾部指針
public DoublyLinkedList() { }
public T peekHead() {
if (head != null) {
return head.data;
}
return null;
}
public boolean isEmpty() {
return head == null;
}
public void insertFirst(T data) {// 插入 到 鏈頭
Linkt newLink = new Linkt(data);
if (isEmpty()) {//為空時，第1次插入的新結點為尾結點
rear = newLink;
} else {
head.previous = newLink; //舊頭結點的上結點等於新結點
}
newLink.next = head; //新結點的下結點舊頭結點
head = newLink; //賦值後，頭結點的下結點是舊頭結點，上結點null
}
public void insertLast(T data) {//在鏈尾 插入
Linkt newLink = new Linkt(data);
if (isEmpty()) {
head = newLink;
} else {
rear.next = newLink;
}
newLink.previous = rear;
rear = newLink; //賦值後，尾結點的上結點是舊尾結點，下結點null
}
public T deleteHead() {//刪除 鏈頭
if (isEmpty()) return null;
Linkt temp = head;
head = head.next; //變更首結點，為下一結點
if (head != null) {
head.previous = null;
} else {
rear = null;
}
return temp.data;
}
public T deleteRear() {//刪除 鏈尾
if (isEmpty()) return null;
Linkt temp = rear;
rear = rear.previous; //變更尾結點，為上一結點
if (rear != null) {
rear.next = null;
} else {
head = null;
}
return temp.data;
}
public T find(T t) {//從頭到尾find
if (isEmpty()) {
return null;
}
Linkt find = head;
while (find != null) {
if (!find.data.equals(t)) {
find = find.next;
} else {
break;
}
}
if (find == null) {
return null;
}
return find.data;
}
public T delete(T t) {
if (isEmpty()) {
return null;
}
Linkt current = head;
while (!current.data.equals(t)) {
current = current.next;
if (current == null) {
return null;
}
}
if (current == head) {
head = head.next;
if (head != null) {
head.previous = null;
}
} else if (current == rear) {
rear = rear.previous;
if (rear != null) {
rear.next = null;
}
} else {
//中間的非兩端的結點，要移除current
current.next.previous = current.previous;
current.previous.next = current.next;
}
return current.data;
}
public boolean insertAfter(T key, T data) {//插入在key之後, key不存在return false
if (isEmpty()) {
return false;
}
Linkt current = head;
while (!current.data.equals(key)) {
current = current.next;
if (current == null) {
return false;
}
}
Linkt newLink = new Linkt(data);
if (current == rear) {
rear = newLink;
} else {
newLink.next = current.next;
current.next.previous = newLink;
}
current.next = newLink;
newLink.previous = current;
return true;
}
public void displayList4Head() {//從頭開始遍歷
System.out.println(“List (first–last):”);
Linkt current = head;
while (current != null) {
current.displayLink();
current = current.next;
}
}
public void displayList4Rear() {//從尾開始遍歷
System.out.println(“List (last–first):”);
Linkt current = rear;
while (current != null) {
current.displayLink();
current = current.previous;
}
}
class Linkt {//鏈結點
T data; //數據域
Linkt next; //後繼指針，結點 鏈域
Linkt previous; //前驅指針，結點 鏈域
Link(T data) {
this.data = data;
}
void displayLink() {
System.out.println(“the data is ” + data.toString());
}
}
public static void main(String[] args) {
DoublyLinkedListinteger list = new DoublyLinkedListinteger();
list.insertLast(1);
list.insertFirst(2);
list.insertLast(3);
list.insertFirst(4);
list.insertLast(5);
list.displayList4Head();
Integer deleteHead = list.deleteHead();
System.out.println(“deleteHead:” + deleteHead);
list.displayList4Head();
Integer deleteRear = list.deleteRear();
System.out.println(“deleteRear:” + deleteRear);
list.displayList4Rear();
System.out.println(“find:” + list.find(6));
System.out.println(“find:” + list.find(3));
System.out.println(“delete find:” + list.delete(6));
System.out.println(“delete find:” + list.delete(1));
list.displayList4Head();
System.out.println(“—-在指定key後插入—-“);
list.insertAfter(2, 8);
list.insertAfter(2, 9);
list.insertAfter(9, 10);
list.displayList4Head();
}
}
java用node還是自己實現鏈表
用node。
javaListNode鏈表就是用Java自定義實現的鏈表結構。
鏈表是一種物理存儲單元上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。鏈表由一系列結點組成，結點可以在運行時動態生成。
用java單鏈表實現一元多項式相加的算法？
public class Test {
public static void main(String[] args) {
try{
LinkList list1 = new LinkList();
LinkList list2 = new LinkList();
LinkList list3 = null;
list1.addAt(0, new Item(1, 5));
list1.addAt(1, new Item(-1.5, 3));
list1.addAt(2, new Item(1, 1));
list2.addAt(0, new Item(0.5, 5));
list2.addAt(1, new Item(0.5, 4));
list2.addAt(2, new Item(1.5, 3));
list2.addAt(3, new Item(3, 0));
list3 = mergeLinkList(list1, list2);
System.out.println(“一元多項式的相加過程：”);
list1.listAll();
System.out.println(” + “);
list2.listAll();
System.out.println(” = “);
list3.listAll();
}
catch(Exception e){
e.printStackTrace();
}
}
/**
* 一元多項式的一般項類
*/
class Item{
private double coef; //一元多項式的一般項的係數
private int exp; //一元多項式的一般項的指數
public Item(){
this.coef = 0.0;
this.exp = 0;
}
public Item(double coef, int exp){
this.coef = coef;
this.exp = exp;
}
public double getCoef(){
return this.coef;
}
public void setCoef(double coef){
this.coef = coef;
}
public int getExp(){
return this.exp;
}
public void setExp(int exp){
this.exp = exp;
}
}
/**
* 鏈表結點類
*/
class Node{
private Item data;
private Node next; //鏈表結點的指針域，指向直接後繼結點
public Node(){
data = null;
next = null;
}
public Node(Item data, Node next){
this.data = data;
this.next = next;
}
public Item getData(){
return this.data;
}
public void setData(Item data){
this.data = data;
}
public Node getNext(){
return this.next;
}
public void setNext(Node next){
this.next = next;
}
}
/**
* 鏈表類
*/
class LinkList{
private Node head = null; //頭結點指針
private int size = 0;
public LinkList(){
head = new Node();
size = 0;
}
//在i位置插入元素elem
public boolean addAt(int i, Item elem) {
if(i 0 || i size){
return false;
}
Node pre,curr;
int pos;
for(pre=head; i0 pre.getNext()!=null; i–,pre=pre.getNext());
curr = new Node(elem, pre.getNext());
pre.setNext(curr);
size++;
return true;
}
//刪除i位置的元素
public boolean removeAt(int i) {
if(i 0 || i = size){
return false;
}
Node pre,curr;
for(pre=head; i0 pre.getNext()!=null; i–,pre=pre.getNext());
curr = pre.getNext();
pre.setNext(curr.getNext());
size–;
return true;
}
java是一種可以撰寫跨平台應用軟件的面向對象的程序設計語言。Java 技術具有卓越的通用性、高效性、平台移植性和安全性，廣泛應用於PC、數據中心、遊戲控制台、科學超級計算機、流動電話和互聯網，同時擁有全球最大的開發者專業社群。
在Java中如何實現雙向鏈表?
雙向鏈表：就是有雙向指針，即雙向的鏈域。\x0d\x0a鏈結點的結構：\x0d\x0a┌────┬────┬────────┐\x0d\x0a│ data │ next │ previous │\x0d\x0a└────┴────┴────────┘\x0d\x0a雙向鏈表不必是雙端鏈表(持有對最後一個鏈結點的引用)，雙端鏈表插入時是雙向的。\x0d\x0a有兩條鏈：一條從頭到尾，一條從尾到頭，刪除遍歷時也是雙向的。\x0d\x0a/**\x0d\x0a * 雙向鏈表\x0d\x0a */\x0d\x0apublic class DoublyLinkedList {\x0d\x0a private Link head; //首結點\x0d\x0a private Link rear; //尾部指針\x0d\x0a public DoublyLinkedList() { }\x0d\x0a public T peekHead() {\x0d\x0a if (head != null) {\x0d\x0a return head.data;\x0d\x0a }\x0d\x0a return null;\x0d\x0a }\x0d\x0a public boolean isEmpty() {\x0d\x0a return head == null;\x0d\x0a }\x0d\x0a public void insertFirst(T data) {// 插入 到 鏈頭\x0d\x0a Link newLink = new Link(data);\x0d\x0a if (isEmpty()) {//為空時，第1次插入的新結點為尾結點\x0d\x0a rear = newLink;\x0d\x0a } else {\x0d\x0a head.previous = newLink; //舊頭結點的上結點等於新結點\x0d\x0a }\x0d\x0a newLink.next = head; //新結點的下結點舊頭結點\x0d\x0a head = newLink; //賦值後，頭結點的下結點是舊頭結點，上結點null\x0d\x0a }\x0d\x0a public void insertLast(T data) {//在鏈尾 插入\x0d\x0a Link newLink = new Link(data);\x0d\x0a if (isEmpty()) {\x0d\x0a head = newLink;\x0d\x0a } else {\x0d\x0a rear.next = newLink;\x0d\x0a }\x0d\x0a newLink.previous = rear;\x0d\x0a rear = newLink; //賦值後，尾結點的上結點是舊尾結點，下結點null\x0d\x0a }\x0d\x0a public T deleteHead() {//刪除 鏈頭\x0d\x0a if (isEmpty()) return null;\x0d\x0a Link temp = head;\x0d\x0a head = head.next; //變更首結點，為下一結點\x0d\x0a if (head != null) {\x0d\x0a head.previous = null;\x0d\x0a } else {\x0d\x0a rear = null;\x0d\x0a }\x0d\x0a return temp.data;\x0d\x0a }\x0d\x0a public T deleteRear() {//刪除 鏈尾\x0d\x0a if (isEmpty()) return null;\x0d\x0a Link temp = rear;\x0d\x0a rear = rear.previous; //變更尾結點，為上一結點\x0d\x0a if (rear != null) {\x0d\x0a rear.next = null;\x0d\x0a } else {\x0d\x0a head = null;\x0d\x0a }\x0d\x0a return temp.data;\x0d\x0a }\x0d\x0a public T find(T t) {//從頭到尾find\x0d\x0a if (isEmpty()) {\x0d\x0a return null;\x0d\x0a }\x0d\x0a Link find = head;\x0d\x0a while (find != null) {\x0d\x0a if (!find.data.equals(t)) {\x0d\x0a find = find.next;\x0d\x0a } else {\x0d\x0a break;\x0d\x0a }\x0d\x0a }\x0d\x0a if (find == null) {\x0d\x0a return null;\x0d\x0a }\x0d\x0a return find.data;\x0d\x0a }\x0d\x0a public T delete(T t) {\x0d\x0a if (isEmpty()) {\x0d\x0a return null;\x0d\x0a }\x0d\x0a Link current = head;\x0d\x0a while (!current.data.equals(t)) {\x0d\x0a current = current.next;\x0d\x0a if (current == null) {\x0d\x0a return null;\x0d\x0a }\x0d\x0a }\x0d\x0a if (current == head) {\x0d\x0a head = head.next;\x0d\x0a if (head != null) {\x0d\x0a head.previous = null;\x0d\x0a }\x0d\x0a } else if (current == rear) {\x0d\x0a rear = rear.previous;\x0d\x0a if (rear != null) {\x0d\x0a rear.next = null;\x0d\x0a }\x0d\x0a } else {\x0d\x0a //中間的非兩端的結點，要移除current\x0d\x0a current.next.previous = current.previous;\x0d\x0a current.previous.next = current.next;\x0d\x0a }\x0d\x0a return current.data;\x0d\x0a }\x0d\x0a public boolean insertAfter(T key, T data) {//插入在key之後, key不存在return false\x0d\x0a if (isEmpty()) {\x0d\x0a return false;\x0d\x0a }\x0d\x0a Link current = head;\x0d\x0a while (!current.data.equals(key)) {\x0d\x0a current = current.next;\x0d\x0a if (current == null) {\x0d\x0a return false;\x0d\x0a }\x0d\x0a }\x0d\x0a Link newLink = new Link(data);\x0d\x0a if (current == rear) {\x0d\x0a rear = newLink;\x0d\x0a } else {\x0d\x0a newLink.next = current.next;\x0d\x0a current.next.previous = newLink;\x0d\x0a }\x0d\x0a current.next = newLink;\x0d\x0a newLink.previous = current;\x0d\x0a return true;\x0d\x0a }\x0d\x0a public void displayList4Head() {//從頭開始遍歷\x0d\x0a System.out.println(“List (first–last):”);\x0d\x0a Link current = head;\x0d\x0a while (current != null) {\x0d\x0a current.displayLink();\x0d\x0a current = current.next;\x0d\x0a }\x0d\x0a }\x0d\x0a public void displayList4Rear() {//從尾開始遍歷\x0d\x0a System.out.println(“List (last–first):”);\x0d\x0a Link current = rear;\x0d\x0a while (current != null) {\x0d\x0a current.displayLink();\x0d\x0a current = current.previous;\x0d\x0a }\x0d\x0a }\x0d\x0a\x0d\x0a class Link {//鏈結點\x0d\x0a T data; //數據域\x0d\x0a Link next; //後繼指針，結點 鏈域\x0d\x0a Link previous; //前驅指針，結點 鏈域\x0d\x0a Link(T data) {\x0d\x0a this.data = data;\x0d\x0a }\x0d\x0a void displayLink() {\x0d\x0a System.out.println(“the data is ” + data.toString());\x0d\x0a }\x0d\x0a }\x0d\x0a public static void main(String[] args) {\x0d\x0a DoublyLinkedList list = new DoublyLinkedList();\x0d\x0a list.insertLast(1);\x0d\x0a list.insertFirst(2);\x0d\x0a list.insertLast(3);\x0d\x0a list.insertFirst(4);\x0d\x0a list.insertLast(5);\x0d\x0a list.displayList4Head();\x0d\x0a Integer deleteHead = list.deleteHead();\x0d\x0a System.out.println(“deleteHead:” + deleteHead);\x0d\x0a list.displayList4Head();\x0d\x0a Integer deleteRear = list.deleteRear();\x0d\x0a System.out.println(“deleteRear:” + deleteRear);\x0d\x0a list.displayList4Rear();\x0d\x0a System.out.println(“find:” + list.find(6));\x0d\x0a System.out.println(“find:” + list.find(3));\x0d\x0a System.out.println(“delete find:” + list.delete(6));\x0d\x0a System.out.println(“delete find:” + list.delete(1));\x0d\x0a list.displayList4Head();\x0d\x0a System.out.println(“—-在指定key後插入—-“);\x0d\x0a list.insertAfter(2, 8);\x0d\x0a list.insertAfter(2, 9);\x0d\x0a list.insertAfter(9, 10);\x0d\x0a list.displayList4Head();\x0d\x0a }\x0d\x0a}
原創文章，作者：ISLE，如若轉載，請註明出處：https://www.506064.com/zh-hk/n/140138.html
微信掃一掃 
支付寶掃一掃 