后端开发 \ Java \ Lava链表(双向链表---接口实现)

Lava链表(双向链表---接口实现)

总点击39
简介:在Java中连标配的结点需要用类来封装,下面的简单的双向链表实现: classNode {

在Java中连标配的结点需要用类来封装,下面的简单的双向链表实现:

class Node

{

private Object data;

private Node next;

public Node(Object data) {

this.data = data;

}

public Object getData() {

return data;

}

public Node getNext() {

return next;

}

public void setData(Object data) {

this.data = data;

}

public void setNext(Node next) {

this.next = next;

}

}

public class Link

{

public static void main(String[] args)

{

Node head=new Node("世界");

Node first1=new Node("pick");

Node first2=new Node(1019);

Node tail=new Node("happy");

head.setNext(first1); //在主类中进行链表的链接和插入

first1.setNext(first2);

first2.setNext(tail);

print(head);

}

public static void print(Node node)

{

if(node==null)

return ;

System.out.println(node.getData());

node=node.getNext();

print(node);

}

}

以上代码是在客户端中进行链表的链接,而客户端中并不用看到具体的链接过程,只需要插入数据或者其他具体操作,所以需要用一个类来进行Node类数据的保存和链表之间的链接;但是客户端只需要进行插入数据等,并不关心是通过何种数据结构实现,但是对于客户端需求有很多数据结构实现,为了操作标准化,定义一个接口。代码如下:

package CODE;

import javafx.beans.binding.ObjectBinding;

import jdk.nashorn.internal.ir.UnaryNode;

import org.omg.CORBA.OBJ_ADAPTER;

import javax.management.ObjectName;

////双向链表

interface Ilink

{

boolean add(Object data); //添加

boolean remove(Object data); //删除数据为data的结点

void printLink(); //遍历该链表

int size(); //结点个数

Object set(int index ,Object newdata);// 把索引index所在位置元素替换为newdata,返回原来数据

int contains(Object data);//判断data是否在链表中

Object get(int index);//根据下标返回结点内容

void clear();//销毁

Object[] toArray();//将链表转为数组

}

class LinkImpl implements Ilink

{

private Node head;//头结点

private Node tail; //尾结点

private int size; //结点个数

private class Node //定义为内部类是一种封装

//将每个结点定义为私有内部类,目的内部类和外部类可以访问彼此的私有属性,而且客户端不知道每个结点具体情况,

{

Node prev;

private Object data;

Node next;

public Node(Node prev, Object data,Node next) //结点的构造方法

{

this.prev=prev;

this.data=data;

this.next=next;

}

}

public boolean add(Object data)

{

//利用尾插

Node prev=this.tail;

Node newnode=new Node(this.tail,data,null);

if(this.head==null) //第一次插入时头为为空,将头尾都指向newnode

this.head=newnode;

else

{

prev.next=newnode;

}

this.tail=newnode;

this.size++;

return true;

}

public boolean remove(Object data)

{

if(data==null) //很有可能这个节点数据为null,但是对于数据不是null的节点,比较用的是equals,所以需要分开判断

{

for (Node tmp = head; tmp != null; tmp = tmp.next)

{

if(tmp.data==null) //找到该节点

{

if(Unlink(tmp)) //删除该节点

return true;

}

}

return false;

}

else {

for (Node tmp = head; tmp != null; tmp = tmp.next) {

if (data.equals(tmp.data)) {

if (Unlink(tmp))

return true;

}

}

return false;

}

}

public Object set(int index, Object newdata) //替换数据

{

if(isIndex(index)) //首先下标是合法的

{

Node tmp=getNode(index);

Object olddata=tmp.data;

tmp.data=newdata;

return olddata;

}

return null;

}

public int contains(Object data)

{

if(data==null)

{

int i=0;

for(Node tmp=head;tmp!=null;tmp=tmp.next) {

if (tmp.data == null)

return i;

else

i++;

}

}

else

{

int i=0;

for(Node tmp=head;tmp!=null;tmp=tmp.next)

{

if(data.equals(tmp.data))

return i;

else

i++;

}

}

return -1;

}

private boolean Unlink(Node node)//删除node结点

{

//既然要删除一个结点,是将prev和next链接在一起,那么对prev 是否为空进行操作,next是否为空进行操作

Node prev=node.prev;

Node next=node.next;

if(prev==null)

{

this.head=next;

//head.prev=null; //不能有该语句,如果next为空

}

else

{

prev.next=next;

node.prev=null; //相当于清除该节点的prev

}

if(next==null) //删除尾结点 如果删除的仅有结点,即既是头结点也是为节点,会走这一句

{

this.tail=prev;

}

else

{

next.prev=prev;

node.next=null; //相当于清除该节点的next

}

node.data=null; //将该节点数据置空

this.size--;

return true;

}

public Object get(int index) //返回索引为index的数据

{

if(isIndex(index))

{

Node tmp=getNode(index);

return tmp.data;

}

System.out.println("下标不合法");

return null;

}

public void printLink() //遍历链表

{

for(Node tmp=head;tmp!=null;tmp=tmp.next)

{

System.out.println(tmp.data);

}

}

public void clear() //销毁链表

{

for(Node tmp=head;tmp!=null;)

{

Node next=tmp.next;

tmp.next=null;

tmp.prev=null;

tmp.data=null;

tmp=null;

tmp=next;

size--;

}

head=tail=null;

}

public int size()

{

return size;

}

public Object[] toArray() //将链表转为数组

{

if(size!=0)

{

Object[] linkArray=new Object[this.size];

int index=0;

for(Node tmp=head;tmp!=null;tmp=tmp.next)

{

linkArray[index]=tmp.data;

index++;

}

return linkArray;

}

return null;

}

private boolean isIndex(int index) //判断下标是否合法

{

return index>=0 && index<size;

}

private Node getNode(int index) //返回下标所在的结点

{

if(index<size/2) //元素的一半,从head向尾找

{

Node start=head;

for(int i=0;i<index;i++)

{

start=start.next;

}

return start;

}

else

{

Node end=tail;

for(int i=size-1;i>index;i--)

{

end=end.prev;

}

return end;

}

}

}

class factory //一个工厂专门生产对象,这样在客户端就不用new对象

{

public static LinkImpl getLink()

{

return new LinkImpl();

}

}

public class DoubleLink

{

public static void main(String[] args)

{

Ilink l=factory.getLink();

l.add("pick");

l.add("hello");

l.add(null);

System.out.println(l.set(2,19));

l.printLink();

System.out.println("*************"+l.size());

l.remove("pick");

l.remove(null);

l.printLink();

System.out.println(l.get(1));

System.out.println("*************");

l.clear();

l.printLink();

System.out.println(l.size());

}

}

Lava链表(双向链表---接口实现)

意见反馈 常见问题 官方微信 返回顶部