Java单链表(双端链表)简单实现

时间:2022-12-10 17:37:00

1、节点数据结构

public class LinkNode {
public int data;
public LinkNode next;

public LinkNode(){

}

public LinkNode(int value){
this.data = value;
this.next = null;
}
}

2、单链表实现

public class SingleLink {

public LinkNode head;

public SingleLink(){
head = new LinkNode();
head.next = null;
}

public void insertFirst(int value){
LinkNode newLink = new LinkNode(value);
if(head.next == null){
head.next = newLink;
} else {
LinkNode temp = head.next;
head.next = newLink;
newLink.next = temp;
}
}

public int deleteFirst(){
if(isEmpty())
throw new EmptyLinkException("current link is empty");
LinkNode temp = head.next;
head.next = head.next.next;
return temp.data;
}

public LinkNode find(int value){
if(isEmpty())
throw new EmptyLinkException("current link is empty");
LinkNode temp = head.next;
while(temp != null){
if(value == temp.data){
break;
}
temp = temp.next;
}

return temp;
}

public void displayLink(){
LinkNode temp = head.next;
while(temp != null){
System.out.println(temp.data);
temp = temp.next;
}
}

public boolean isEmpty(){
return (head.next == null);
}

/**
* @param args
*/

public static void main(String[] args) {
Random random = new Random();
SingleLink singleLink = new SingleLink();
for(int i=0;i<10;i++){
singleLink.insertFirst(random.nextInt(100));
}
singleLink.displayLink();
int temp = random.nextInt(100);
System.out.println("try to find: " + temp);
System.out.println(singleLink.find(temp) == null?"not found":singleLink.find(temp).data);
for(int i=0;i<10;i++){
System.out.println(singleLink.deleteFirst());
}
}
}

3、注意
(1)双端链表是在单链表基础上增加一个对链表最后一个节点的引用
(2)双端链表可以增加一个insertLast方法
(3)双端链表【不能】解决从链表末端删除节点的问题

双向链表可以在头部和尾部进行节点【添加】和【删除】操作