1.先定義一個節(jié)點類
創(chuàng)新互聯(lián)公司成都網(wǎng)站建設(shè)定制設(shè)計，是成都網(wǎng)站營銷推廣公司,為鑿毛機(jī)提供網(wǎng)站建設(shè)服務(wù),有成熟的網(wǎng)站定制合作流程，提供網(wǎng)站定制設(shè)計服務(wù)：原型圖制作、網(wǎng)站創(chuàng)意設(shè)計、前端HTML5制作、后臺程序開發(fā)等。成都網(wǎng)站改版熱線：18982081108
package com.buren;
public class IntNode {
//定義一個節(jié)點類
int
info;
//定義屬性，節(jié)點中的值
IntNode next;
//定義指向下一個節(jié)點的屬性
public IntNode(int
i){ //構(gòu)造一個next為空的節(jié)點
this(i,null);
}
public IntNode(int i,IntNode
n){ //構(gòu)造值為i指向n的節(jié)點
info=i;
next=n;
}
}
2.再定義一個鏈表類，這是主要部分
package com.buren;
public class IntSLList {
private IntNode head,tail;
//定義指向頭結(jié)點和尾結(jié)點的指針，
//如果大家看著這個不像指針的話，那就需要對指針有更深刻的了解
public
IntSLList(){
//定義一個空節(jié)點
head=tail=null;
}
public boolean
isEmpty(){
//判斷節(jié)點是否為空
return
head==null;
//這行代碼看起來似乎很神奇，其實真的很神奇，偶是服了
}
public void addToHead(int el){
//將el插入到頭結(jié)點前
head=new
IntNode(el,head);
//將節(jié)點插入到頭結(jié)點前，作為新的投節(jié)點
if(head==tail){
//給空鏈表插入節(jié)點時
tail=head;
//頭結(jié)點和尾結(jié)點指向同一個節(jié)點
}
}
public void addToTail(int
el){
//向鏈表的尾部增加結(jié)點
if(!isEmpty()){
//判斷鏈表是否為空
tail.next=new
IntNode(el);
//新建立一個值為el的節(jié)點，將鏈表的尾結(jié)點指向新節(jié)點
tail=tail.next;
//更新尾指針的指向
}else{
head=tail=new
IntNode(el);
//如果鏈表為空，新建立一個節(jié)點，將頭尾指針同時指向這個節(jié)點
}
}
public int
deleteFromHead(){
//刪除頭結(jié)點，將節(jié)點信息返回
int
el=head.info;
//取出節(jié)點信息
if(head==tail){
//如果鏈表中只有一個節(jié)點
head=tail=null;
//刪除這一個節(jié)點
}else{
head=head.next;
//如果鏈表中不止一個節(jié)點，將頭結(jié)點的下一個節(jié)點作為頭結(jié)點
}
return
el;
//返回原頭結(jié)點的值
}
public int
deleteFromTail(){
//刪除尾結(jié)點，返回尾結(jié)點的信息
int
el=tail.info;
//取出尾結(jié)點的值
if(head==tail){
// 如果鏈表中只有一個節(jié)點
head=tail=null;
//刪除這個節(jié)點
}else{
IntNode
temp;
//定義中間變量
for(temp=head;temp.next!=tail;temp=temp.next);
//找出尾結(jié)點的前一個節(jié)點，注意最后的分號，
//這個for循環(huán)是沒有循環(huán)體的，目的在于找出尾結(jié)點的前一個節(jié)點
//在整個程序中用了很多次這樣的寫法，相當(dāng)經(jīng)典啊
tail=temp;
//將找出來的節(jié)點作為尾結(jié)點，刪除原來的尾結(jié)點
tail.next=null;
//將新尾結(jié)點的指向設(shè)為空
}
return
el;
//返回原尾結(jié)點的信息
}
public void
printAll(){
//打印鏈表中所有節(jié)點的信息
if(isEmpty()){
//如果鏈表為空
System.out.println("This
list is
empty!");
//輸出提示信息
return;
//返回到調(diào)用的地方
}
if(head==tail){
//當(dāng)鏈表中只有一個節(jié)點時
System.out.println(head.info);
//輸出這個節(jié)點的信息，就是頭結(jié)點的信息
return;
}
IntNode
temp;
//定義一個中間變量
for(temp=head;temp!=null;temp=temp.next){
//遍歷整個鏈表
System.out.print(temp.info+"
");
//輸出每個節(jié)點的信息
}
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的節(jié)點
if(head.info==el
head==tail){
//如果只有一個節(jié)點，并且節(jié)點的值為el
head=tail=null;
//刪除這個節(jié)點
}else
if(head.info==el){
// 不止一個節(jié)點，而頭結(jié)點的值就是el
head=head.next;
//刪除頭結(jié)點
}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指向的節(jié)點刪除，最好畫一個鏈表的圖，有助于理解
if(temp==tail){
//如果temp指向的節(jié)點是尾結(jié)點
tail=pred;
//將pred指向的節(jié)點設(shè)為尾結(jié)點，
}
}
}
//下面這個方法是在鏈表中值為el1的節(jié)點前面插入一個值為el2的節(jié)點，
//用類似的思想可以再寫一個在鏈表中值為el1的節(jié)點后面插入一個值為el2的節(jié)點
public boolean insertToList(int el1,int
el2){
//定義一個插入節(jié)點的方法，插入成功返回true，否則返回false
IntNode
pred,temp; //定義兩個中間變量
if(isEmpty()){
//判斷鏈表是否為空
return
false;
//如果鏈表為空就直接返回false
}
if(head.info==el1
head==tail){
//如果鏈表中只有一個節(jié)點，并且這個節(jié)點的值是el1
head=new
IntNode(el2,head);
//新建立一個節(jié)點
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));
}
}
/*
注意：鏈表的結(jié)點數(shù)量用size表示，結(jié)點的位置為0~size-1
*/
import java.util.Scanner;
public class Test7 {
public static void main(String[] args) {
try{
LinkList list = new LinkList();
Integer value;
int pos = 0;
Scanner input = new Scanner(System.in);
String choice = null;
//測試A
while(true){
System.out.print("請輸入待插入結(jié)點的值(x或X退出)：");
choice = input.next();
if(choice.toUpperCase().equals("X")){
break;
}
value = Integer.valueOf(choice);
if(list.addAt(pos, value) == true){
System.out.println("插入值為 " + value + " 的結(jié)點到當(dāng)前鏈表成功!");
pos++;
}
else{
System.out.println("插入結(jié)點失敗!");
}
}
System.out.print("當(dāng)前鏈表所有結(jié)點：");
list.listAll();
//測試B
while(true){
System.out.print("請輸入待查詢結(jié)點的值(x或X退出)：");
choice = input.next();
if(choice.toUpperCase().equals("X")){
break;
}
value = Integer.valueOf(choice);
pos = list.findByValue(value);
if(pos == -1){
System.out.println("當(dāng)前鏈表中不存在值為 " + value + " 的結(jié)點");
}
else{
System.out.println("值為 " + value + " 的結(jié)點在當(dāng)前鏈表中的位置為 " + pos);
}
}
//測試C
while(true){
System.out.print("請輸入待刪除結(jié)點的位置[0~" + (list.getSize()-1) + "](x或X退出)：");
choice = input.next();
if(choice.toUpperCase().equals("X")){
break;
}
pos = Integer.valueOf(choice);
if(list.removeAt(pos) == true){
System.out.println("刪除當(dāng)前鏈表中 " + pos + " 位置的結(jié)點成功!");
}
else{
System.out.println("刪除結(jié)點失敗!");
}
}
System.out.print("當(dāng)前鏈表所有結(jié)點：");
list.listAll();
}
catch(Exception e){
e.printStackTrace();
}
}
}
/**
* 鏈表結(jié)點類
*/
class Node{
private Object data; //鏈表結(jié)點的數(shù)據(jù)域
private Node next; //鏈表結(jié)點的指針域，指向直接后繼結(jié)點
public Node(){
data = null;
next = null;
}
public Node(Object data, Node next){
this.data = data;
this.next = next;
}
public Object getData(){
return this.data;
}
public void setData(Object data){
this.data = data;
}
public Node getNext(){
return this.next;
}
public void setNext(Node next){
this.next = next;
}
}
/**
* 鏈表類
*/
class LinkList{
private Node head = null; //頭結(jié)點指針
private int size = 0;
public LinkList(){
head = new Node();
size = 0;
}
//在i位置插入元素elem
public boolean addAt(int i, Object 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;
}
//根據(jù)值value查詢結(jié)點是否存在，若存在返回位置，否則返回-1
public int findByValue(Object value){
Node curr;
int pos;
for(pos=0,curr=head.getNext(); curr!=null; pos++,curr=curr.getNext()){
if(curr.getData().toString().equals(value.toString())){
break;
}
}
if(curr==null){
return -1;
}
return pos;
//return (curr!=null ? pos : -1);
}
public int getSize(){
return size;
}
public boolean isEmpty(){
return (size==0);
}
public void listAll(){
for(Node curr=head.getNext(); curr!=null; curr=curr.getNext()){
System.out.print(curr.getData() + "\t");
}
System.out.println();
}
}
雙向鏈表：就是有雙向指針，即雙向的鏈域。\x0d\x0a鏈結(jié)點的結(jié)構(gòu)：\x0d\x0a┌────┬────┬────────┐\x0d\x0a│ data │ next │ previous │\x0d\x0a└────┴────┴────────┘\x0d\x0a雙向鏈表不必是雙端鏈表(持有對最后一個鏈結(jié)點的引用)，雙端鏈表插入時是雙向的。\x0d\x0a有兩條鏈：一條從頭到尾，一條從尾到頭，刪除遍歷時也是雙向的。\x0d\x0a/**\x0d\x0a * 雙向鏈表\x0d\x0a */\x0d\x0apublic class DoublyLinkedList {\x0d\x0a private Link head; //首結(jié)點\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次插入的新結(jié)點為尾結(jié)點\x0d\x0a rear = newLink;\x0d\x0a } else {\x0d\x0a head.previous = newLink; //舊頭結(jié)點的上結(jié)點等于新結(jié)點\x0d\x0a }\x0d\x0a newLink.next = head; //新結(jié)點的下結(jié)點舊頭結(jié)點\x0d\x0a head = newLink; //賦值后，頭結(jié)點的下結(jié)點是舊頭結(jié)點，上結(jié)點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; //賦值后，尾結(jié)點的上結(jié)點是舊尾結(jié)點，下結(jié)點null\x0d\x0a }\x0d\x0a public T deleteHead() {//刪除 鏈頭\x0d\x0a if (isEmpty()) return null;\x0d\x0a Link temp = head;\x0d\x0a head = head.next; //變更首結(jié)點，為下一結(jié)點\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; //變更尾結(jié)點，為上一結(jié)點\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 //中間的非兩端的結(jié)點，要移除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 {//鏈結(jié)點\x0d\x0a T data; //數(shù)據(jù)域\x0d\x0a Link next; //后繼指針，結(jié)點 鏈域\x0d\x0a Link previous; //前驅(qū)指針，結(jié)點 鏈域\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}
java中創(chuàng)建鏈表的例子：
package zx;
class Link{
private Node root;
class Node{
private String name;
private Node Next;
public Node(String name){
this.name = name;
}
public String getName(){
return this.name;
}
public void addNode(Node newNode){
if(this.Next==null){
this.Next = newNode;
}else{
this.Next.addNode(newNode);
}
}
public void printNode(){
System.out.print(this.name + "--");
if(this.Next!=null){
this.Next.printNode();
}
}
};
public void add(String name){
Node newNode = new Node(name);
if(this.root==null){
this.root = newNode;
}else{
this.root.addNode(newNode);
}
}
public void print(){
if(this.root!=null){
this.root.printNode();
}
}
};
public class LinkDemo {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Link link = new Link();
link.add("根節(jié)點");
link.add("第一節(jié)點");
link.add("第二節(jié)點");
link.add("第三節(jié)點");
link.add("第四節(jié)點");
link.print();
System.out.println("null");
}
}
//如果感興趣的話，可以把下面的改成泛型的也就是這樣的
//一個學(xué)生的類
public class Stu(){
String name;
int age;
public Stu(String name,int age){
this.name=name;
this.age=age;
}
}
//創(chuàng)建兩個學(xué)生的對像
Stu stu1=new Stu("weiwie",24);
Stu stu2=new Stu("xiaoqiang",25);
//創(chuàng)建集合類,存放的是Stu對像,這樣的聲明只能存Stu對像
List Stu list=new ArrayListStu();
//存數(shù)據(jù)
list.add(stu1);
list.add(stu2);
//遍歷
for(int i=0;ilist.size();i++){
//向下轉(zhuǎn)型方便了,取出來的就是Stu對像
Stu stu=list.get(i);
}
List list=new ArrayList();
list.add("對像");
遍歷
for(int i=0;ilist.size();i++){
//需要強(qiáng)轉(zhuǎn)
String str=(String)list.get(i);
得到你存放的數(shù)據(jù)
}
Map map=new HashMap();
//存值
map.put("one","對像");
//取值
String str=(String)map.get("one");
Set set=new HashSet();
//存值
set.add("對像");
//需要用這個對像遍歷
Iterator iter=set.iterator();
while(iter.hasNext()){
//取值
String Str=(String)iter.next();
}
重慶分公司
重慶分公司
