双向链表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 什么是单向链表 和 双向链表
链表是类似一种数据结构的东西，就是分别存放有地址以及数据单项链表一般是上一个存放地址的地方存放下一个节点的地址，而双向的就是有两个存放地址的地方，分别存上一个以及下一个的地址。大概是这样子