当前位置：首页 » 编程语言 » 双向链表java

双向链表java

发布时间: 2021-03-17 18:18:00

⑴ 用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));

}
}

⑵ java 什么是单向链表和双向链表

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

⑶ java中双向链表是什么意思啊，是用来干啥的啊，求大神解答谢谢

采用双向循环链表作为数据结构
1 新元素的下一个指向header
2 新元素的上一个指向header的上一个
3 新元素的上一个的下一个指向新元素
4 新元素的下一个的上一个指向新元素
一般LinkedList是采用双向循环链表，无需扩容，添加元素添加到最后即可

⑷ （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

⑸ 双向循环链表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();
}
}

⑹ java数据结构--实现双链表

调换了出了什么问题了吗？调换后应该结果不变的。你的循环有问题的p.next != null第一个版节点却是ew Node(e,null,null); 明显下个的权节点就是null啊，这样写永远都只有一个节点的。

⑺ java 中用双向链表模拟栈

这里只是实现了Stack的部分功能

public class Stack{

private Node top;

public Stack(){
this.top = null;
}

public void push(Node node){
if(node == null)
return;
if(this.top == null){
this.top = node;
node.setNext(null);
node.setPre(null);
}
else{
this.top.setNext(node);
node.setPre(this.top);
node.setNext(null);
this.top = node;
}
}

public Node pop(){
if(this.top == null)
return null;
Node curr = this.top;
Node pre = curr.getPre();
pre.setNext(null);
this.top = pre;
return curr;
}

public Node top(){
return this.top;
}

public boolean isEmpty(){
return this.top == null ? true : false;
}

public void empty(){
this.top = null;
}

public static void main(String[] args){
Stack stack = new Stack();
Node n1 = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);

System.out.println(stack.isEmpty());
stack.push(n1);
System.out.println(stack.top().getValue());
stack.push(n2);
stack.push(n3);
System.out.println(stack.pop().getValue());
stack.empty();
}
}

class Node {
private int value;
private Node next;
private Node pre;

public Node(int value, Node next, Node pre){
this.value = value;
this.next = next;
this.pre = pre;
}

public Node(int value){
this.value = value;
this.next = null;
this.pre = null;
}

public int getValue() {
return value;
}

public void setValue(int value) {
this.value = value;
}

public Node getNext() {
return next;
}

public void setNext(Node next) {
this.next = next;
}

public Node getPre() {
return pre;
}

public void setPre(Node pre) {
this.pre = pre;
}
}

⑻ 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!
处理已完成。

⑼ 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;
}

⑽ 在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();
}
}

阅读全文

双向链表java

与双向链表java相关的阅读推荐