雙向鏈表java
A. 在java中如何實現雙向鏈表
雙向鏈表：就是有雙向指針，即雙向的鏈域。
鏈結點的結構：
┌────┬────┬────────┐
│ data │ next │ previous │
└────┴────┴────────┘
雙向鏈表不必是雙端鏈表(持有對最後一個鏈結點的引用)，雙端鏈表插入時是雙向的。
有兩條鏈：一條從頭到尾，一條從尾到頭，刪除遍歷時也是雙向的。
/**
* 雙向鏈表
*/
public class DoublyLinkedList<t> {
private Link<t> head; //首結點
private Link<t> 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) {// 插入 到 鏈頭
Link<t> newLink = new Link<t>(data);
if (isEmpty()) {//為空時，第1次插入的新結點為尾結點
rear = newLink;
} else {
head.previous = newLink; //舊頭結點的上結點等於新結點
}
newLink.next = head; //新結點的下結點舊頭結點
head = newLink; //賦值後，頭結點的下結點是舊頭結點，上結點null
}
public void insertLast(T data) {//在鏈尾 插入
Link<t> newLink = new Link<t>(data);
if (isEmpty()) {
head = newLink;
} else {
rear.next = newLink;
}
newLink.previous = rear;
rear = newLink; //賦值後，尾結點的上結點是舊尾結點，下結點null
}
public T deleteHead() {//刪除 鏈頭
if (isEmpty()) return null;
Link<t> temp = head;
head = head.next; //變更首結點，為下一結點
if (head != null) {
head.previous = null;
} else {
rear = null;
}
return temp.data;
}
public T deleteRear() {//刪除 鏈尾
if (isEmpty()) return null;
Link<t> 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;
}
Link<t> 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;
}
Link<t> 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;
}
Link<t> current = head;
while (!current.data.equals(key)) {
current = current.next;
if (current == null) {
return false;
}
}
Link<t> newLink = new Link<t>(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):");
Link<t> current = head;
while (current != null) {
current.displayLink();
current = current.next;
}
}
public void displayList4Rear() {//從尾開始遍歷
System.out.println("List (last-->first):");
Link<t> current = rear;
while (current != null) {
current.displayLink();
current = current.previous;
}
}
class Link<t> {//鏈結點
T data; //數據域
Link<t> next; //後繼指針，結點 鏈域
Link<t> previous; //前驅指針，結點 鏈域
Link(T data) {
this.data = data;
}
void displayLink() {
System.out.println("the data is " + data.toString());
}
}
public static void main(String[] args) {
DoublyLinkedList<integer> list = new DoublyLinkedList<integer>();
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();
}
}
B. 用java如何創建一個單鏈表和雙鏈表
單向鏈表
單向鏈表就是通過每個結點的指針指向下一個結點從而鏈接起來的結構。
單向鏈表的初始化：這里我所講的鏈表都是頭結點不參與計算的，也就是說第一個結點都是頭結點後面的第一個結點。所以我要先申明一點，這里我把鏈表的初始化放在了構造函數部分，然後析構函數負責釋放頭結點的內存。
單向鏈表的創建過程：鏈表的創建就是添加結點到鏈表的最後，開始是添加一個結點到head結點後面，然後添加一個結點到上次添加的結點後面，每次新建的結點的指針總是指向NULL指針。從上面的示意圖可以看出，我們需要一個輔助指針一直指向最後一個結點，這個輔助結點就是為了讓每次添加的結點都放置在最後一個位置。
單向鏈表插入結點過程：源代碼中的的插入結點函數我設置了一個指定位置，就是在指定位置插入結點。首先，通過位置變數position讓ptemp結點移動到要插入位置的前一個位置，然後接下來的過程就是和創建鏈表的過程是一樣的，把新建的結點添加到ptemp的後面。這里變數position可以從1到鏈表長度加1，意思就是如果不算頭結點的話有3個結點，那你的position變數就可以從1到4，這是因為ptemp指針可以到第3個結點的位置，所以新建結點的位置就可以到4了。
單向鏈表刪除結點過程：源代碼中的刪除結點函數也有一個指定位置變數，為了刪除指定位置的結點。和插入結點一樣通過變數position把ptemp移動到要刪除結點的前一個位置，然後讓ptemp結點中的指針指向要刪除結點後面的一個結點，也就是ptemp結點的下一個的下一個結點，雖然這個結點可能為空，但是程序還是正常運行。但是這里和插入結點不同的是變數position只能從1到鏈表的長度，是因為ptemp移動到最後一個結點的時候，它的下一個結點為空，所以不不需要參與刪除了。
雙向鏈表
1.聽名字可能就能猜到雙向鏈表就是鏈表結點包含兩個指針，一個指針是指向下一個結點的，另一個指針當然就是指向上一個結點的。
2.雙向鏈表的初始化：由於這里的鏈表頭結點不參與計算，所以頭結點的pPre指針是一直指向NULL指針的。
3.雙向鏈表的創建過程：由於雙向鏈表的每個結點包含兩個指針那麼這個時候我們就要小心處理好每一個指針的指向，要不然會有很多意想不到的錯誤。同樣的，和單向鏈表的創建過程一樣，需要一個輔助指針來指向最後一個結點，然後每新建一個結點，這個結點的pNext指針都是指向NULL指針的，pPre指針指向上一個結點（這是和單向鏈表不同的地方），然後讓上一個指針的pNext指向新建的結點，這樣整個鏈表就連接起來了。
4.雙向鏈表插入結點過程：知道了雙向鏈表的創建過程，那麼插入結點的過程就大同小異 了，有一點需要特別注意的就是這里的變數position范圍也是從1到鏈表長度加1，但是如果待插入的位置是最後一個位置的話，情況就不同了，看到下面的圖我們可以很好的理解，因為沒新建一個結點的時候都需要處理兩個指針，而且新建結點的下一個結點的pPre指針就需要指向這個新建的結點，但是有可能這個新建的結點可能就已經是最後一個結點了，那麼這個時候再執行
ptemp->pNext->pPre=pnew;
這條指令的時候就會報錯了，因為ptemp->pNext已經是個NULL指針了，那空指針哪裡還有pPre呢。因此在程序中要進行一次判斷，看看結點是否是最後一個結點。
5.雙向鏈表刪除結點的過程：要注意的問題和插入結點一樣，看看這個結點是否為NULL。這里就不重復了。
C. 雙向循環鏈表java
我們也做這個，，你是是吧
package KeCheng1;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Iterator;
import java.util.Scanner;
//定義節點類
class Node<AnyType> {
public AnyType data;
public Node<AnyType> prev;
public Node<AnyType> next;
public Node(AnyType d,Node<AnyType> p,Node<AnyType> n){
data=d;
prev=p;
next=n;}}
public class MyLinkedList<AnyType> {
private int theSize;
private Node<AnyType> beginMarker; //頭標記或頭節點
private Node<AnyType> endMarker; //尾標記或尾節點
public MyLinkedList(){
beginMarker=new Node<AnyType>(null,endMarker,endMarker);
endMarker = new Node<AnyType>(null,beginMarker,beginMarker);
beginMarker.next = endMarker;
theSize = 0;}
public int size(){
return theSize;}
public boolean add(AnyType x){
add(size(),x);
return true;}
public void add(int idx,AnyType x){
Node<AnyType> p;
p=getNode(idx);
addBefore(p,x);}
private Node<AnyType> getNode(int idx) {
Node<AnyType> p;
if( idx < 0 || idx > size( ) )
throw new IndexOutOfBoundsException( );
if( idx < size( ) / 2 ) {
p = beginMarker.next;
for( int i = 0; i < idx; i++ )
p = p.next;}
else
{ p = endMarker;
for( int i = size( ); i > idx; i-- )
p = p.prev; }
return p;}
private void addBefore( Node<AnyType> p, AnyType x ) {
Node<AnyType> newNode = new Node<AnyType>( x, p.prev, p );
newNode.prev.next = newNode;
p.prev = newNode;
theSize++;}
public AnyType remove( int idx ){
return remove( getNode(idx));}
private AnyType remove(Node<AnyType> p){
p.next.prev = p.prev;
p.prev.next = p.next;
theSize--;
return p.data;}
public void print(){//輸出鏈表
for(Node<AnyType>x=beginMarker.next;x.next!=beginMarker;x=x.next)
System.out.print(x.data+" ");
System.out.print("\n");}
public AnyType get( int idx ){
return getNode( idx ).data; }
public static void main(String[] args){
MyLinkedList<Integer> La = new MyLinkedList<Integer>();
int Length;
Scanner sc = new Scanner(System.in);
System.out.println("請輸入要創建的雙向鏈表的長度：(大於6)");
Length = sc.nextInt();
System.out.println("請輸入"+Length+"個元素創建La雙向鏈表：");
for(int i=0;i<Length;i++)
{La.add(sc.nextInt());}
System.out.println("輸入的原La雙向鏈表：");
La.print();
System.out.println("在雙向鏈表的第3個位置插入20:");
La.add(3,20);
La.print();
System.out.println("刪除第五位置上的數:");
La.remove(5);
La.print();
System.out.println("插入最後一個節點:99");
La.add(Length,99);
La.print();
System.out.println("插入第一個節點0:");
La.add(0,0);
La.print();
System.out.println("就地逆置:");
int M=Length+2;
int b=0;
for(Length=Length+1;Length>=0;Length--){
int a=La.get(M-1);
La.add(b,a);
b=b+1;
La.remove(M);
}
La.print();
}
}
D. java雙向鏈表
public boolean putAfter(Object obj,DoublyListNode node)//有可能找不到obj,所以我返回boolean
{
DoublyListNode current = head;
while(head.obj!=obj){
current = current.next;
if(current==null)
return false;
}
if(current==tail){
node.next = null;
tail = node;
}else{
node.next = current.next;
current.next.previous = node;
}
node.previous = current;
current.next =node;
return true;
}
public DoublyListNode removeafter(Object obj){//返回了選中的節點
DoublyListNode current = head;
while(current.obj!=obj)
{
current = current.next;
if(current == null)
return null;
}
if(current==head)
head = current.next;
else
current.previous.next = current.next;
if(current == tail)
tail = current.previous;
else
current.next.previous = current.previous;
return current;
}
E. JAVA 單向鏈表 雙向鏈表
看看
http://www..com/s?bs=v&f=8&wd=JAVA+%B5%A5%CF%F2%C1%B4%B1%ED+%CB%AB%CF%F2%C1%B4%B1%ED
//雙向鏈表的簡單表達
public class Mulit {
private class Node
{
private String data;
private Node upNode;
private Node downNode;
public Node()
{
data=null;
upNode=null;
downNode=null;
}
public Node(String newData,Node newDownNode)
{
data=newData;
downNode=newDownNode;
// upNode=newDownNode;
}
}
Node head;
public Mulit()
{
head=null;
}
public void add(String newData)
{
Node lastNode=head;
if(head==null)
head=new Node(newData,head);
else
{
head=new Node(newData,head);
lastNode.upNode=head;
}
}
public void display()
{
Node position =head;
while(position!=null)
{
System.out.print(position.data);
position=position.downNode;
}
}
public void otherDisp()
{
Node position=head;
while(position.downNode!=null)
{
position=position.downNode;
}
//現實的時候有顯示不了最後一個，需要解決
do
{
System.out.print(position.data);
position=position.upNode;
}
while(position.upNode!=null);
}
public static void main (String[] args)
{
Mulit m=new Mulit();
m.add("hello");
m.add("world");
m.add("!");
m.add("");
m.display();
System.out.println();
m.otherDisp();
}
}
生成輸出：
--------------------配置: <--------------------
!worldhello
helloworld!
處理已完成。
F. （java編程）採用雙向鏈表作數據結構，編寫一個通訊錄管理系統。
#include
#include
#include
using namespace std;
#define SIZE 10
struct AddrList
{
string name;
string sex;
int age;
string QQ;
}addrlist[SIZE];
int main()
{
int i;
int j;
cout<<"輸入要輸入的記錄數量:";
cin>>i;
if (i>SIZE)
{
cout<<"輸入的記錄數量大於順序表的最大長度！"<<endl;
return 0;
}
cout<<"輸入格式：\n姓名 性別 年齡 QQ\n"<<endl;
for (j=0;j<i;++j)
{
cout<<"輸入第"<<j+1<<"條記錄"<<endl;
cin>>addrlist[j].name>>addrlist[j].sex>>addrlist[j].age>>addrlist[j].QQ;
}
cout<<"\n姓名\t性別\t年齡\tQQ"<<endl;
for (j=0;j<i;++j)
{
cout<<addrlist[j].name<<"\t"<<addrlist[j].sex<<"\t"<<addrlist[j].age<<"\t"<<addrlist[j].QQ<<endl;
}
return 0;
}
輸入：2
張三 男 23 123456
李四 女 24 66666
G. 用JAVA語言解決：編寫一個鏈表類(雙向鏈表),實現插入,刪除,查找操作
public class DoubleLinkedList
{
// 節點類Node
private static class Node
{
Object value;
Node prev = this;
Node next = this;
Node(Object v)
{
value = v;
}
public String toString()
{
return value.toString();
}
}
private Node head = new Node(null); // 頭節點
private int size; // 鏈表大小
// 以下是介面方法
public boolean addFirst(Object o)
{
addAfter(new Node(o), head);
return true;
}
public boolean addLast(Object o)
{
addBefore(new Node(o), head);
return true;
}
public boolean add(Object o)
{
return addLast(o);
}
public boolean add(int index, Object o)
{
addBefore(new Node(o), getNode(index));
return true;
}
public boolean remove(int index)
{
removeNode(getNode(index));
return true;
}
public boolean removeFirst()
{
removeNode(head.next);
return true;
}
public boolean removeLast()
{
removeNode(head.prev);
return true;
}
public Object get(int index)
{
return getNode(index).value;
}
public int size()
{
return size;
}
public String toString()
{
StringBuffer s = new StringBuffer("[");
Node node = head;
for (int i = 0; i < size; i++)
{
node = node.next;
if (i > 0)
s.append(", ");
s.append(node.value);
}
s.append("]");
return s.toString();
}
private Node getNode(int index)
{
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException();
Node node = head.next;
for (int i = 0; i < index; i++)
node = node.next;
return node;
}
private void addBefore(Node newNode, Node node)
{
newNode.next = node;
newNode.prev = node.prev;
newNode.next.prev = newNode;
newNode.prev.next = newNode;
size++;
}
private void addAfter(Node newNode, Node node)
{
newNode.prev = node;
newNode.next = node.next;
newNode.next.prev = newNode;
newNode.prev.next = newNode;
size++;
}
private void removeNode(Node node)
{
node.prev.next = node.next;
node.next.prev = node.prev;
node.prev = null;
node.next = null;
size--;
}
}
//測試類：
public class Test
{
public static void main(String[] args)
{
DoubleLinkedList dll = new DoubleLinkedList();
//添加
dll.add("張三");
dll.add("李四");
dll.add("王五");
System.out.println(dll);
//添加到最前
dll.addFirst("孫七");
System.out.println(dll);
//添加到最後，同添加
dll.addLast("趙六");
System.out.println(dll);
//添加到指定位置
dll.add(4, "王祖賢");
System.out.println(dll);
//移除最前的
dll.removeFirst();
System.out.println(dll);
//移除最後的
dll.removeLast();
System.out.println(dll);
//移除指定位置上的
dll.remove(2);
System.out.println(dll);
//返回指定位置上的元素
System.out.println(dll.get(1));
}
}
H. java，數據結構雙向鏈表問題
其實 newLink.next = null 可以不寫的 因為 Link newLink = new Link(dd) 這樣的newLink.next 就是null
我看了下源代碼，在insertAfter中寫明是為了和當前插入的元素是在鏈表的最後一位還是在中間插入，這樣是的話newLink.next的值是不同的
if (current == last) // if last link,
{
newLink.next = null; //可以不寫的 ，new出來的就是空。目的是與else的區分
else{
newLink.next = current.next;
}
I. Java 雙向鏈表的迭代器，怎麼添加元素
可以用LinkedList代替你的AdditiveList
LinkedList<String> linklist=new LinkedList<String>();
String [] strs={"1","2","3","4"};
for (String string : strs) {
linklist.add(string);
}
System.out.println("鏈表的第一個元素是 : " + linklist.getFirst());
System.out.println("鏈表最後一個元素是 : " + linklist.getLast());
System.out.println("鏈表的長度 : " + linklist.size());
//然後你需要動態改變鏈表中的元素這時可以用ListIterator<E>迭代器來操作鏈表
ListIterator<String> itr=linklist.listIterator();
while (itr.hasNext()) {
itr.next();//先正序將游標調至結尾
}
while (itr.hasPrevious()) {
String string = (String) itr.previous();//逆序遍歷鏈表
System.out.println(string);
if("2".equals(string)){//在指定位置前插入元素
itr.add("0");//這里就是你需要插入的元素
itr.add("1");
}
}
System.out.println(linklist.toString());
J. java 什麼是單向鏈表 和 雙向鏈表
鏈表是類似一種數據結構的東西，就是分別存放有地址以及數據單項鏈表一般是上一個存放地址的地方存放下一個節點的地址，而雙向的就是有兩個存放地址的地方，分別存上一個以及下一個的地址。大概是這樣子