java单向链表
//单向链表
public class SingleLinkedList {
//链表节点的个数
private int size;
//头节点
private Node head;
public SingleLinkedList() {
size = 0;
head = null;
}
//链表的每个节点类
private class Node {
//每个节点的数据
private Object data;
//每个节点指向下个节点的连接
private Node next;
public Node(Object data) {
this.data = data;
}
}
//在链表头部添加元素
public Object addHead(Object data) {
Node newNode = new Node(data);
if(size == 0) {
head = newNode;
}else {
newNode.next = head;
head = newNode;
}
size ++;
return data;
}
//删除链表头部元素
public Object deleteHead() {
Object data = head.data;
head = head.next;
size -- ;
return data;
}
//查找指定元素，找到返回节点Node,找不到返回null
public Node find(Object data) {
Node current = head;
int tempSize = size;
while(tempSize > 0) {
if(data.equals(current.data)) {
return current;
}else {
current = current.next;
}
tempSize -- ;
}
return null;
}
//删除指定的元素，删除成功返回true
public boolean delete(Object data) {
if(size == 0) {
return false;
}
Node current = head;
Node previous = head;
while( current.data != data) {
if(current.next == null) {
return false;
}else {
previous = current;
current = current.next;
}
}
//如果删除的是第一个节点
if(current == head) {
head = current.next;
size -- ;
}else {//删除的不是第一个节点
previous.next = current.next;
size -- ;
}
return true;
}
//判断链表是否为空
public boolean isEmpty() {
return (size == 0);
}
//显示节点信息
public void display() {
if(size > 0) {
Node node = head;
int tempSize = size;
if(tempSize == 1) {
System.out.print("["+node.data+"]");
return;
}
while(tempSize > 0) {
if(node.equals(head)) {
System.out.print("["+node.data+"->");
}else if(node.next == null) {
System.out.print(node.data+"]");
}else {
System.out.print(node.data+"->");
}
node = node.next;
tempSize --;
}
System.out.println();
}else {
System.out.println("[]");
}
}
}
//单向链表实现栈
public class StackSingleLinke {
private SingleLinkedList linke;
public StackSingleLinke() {
linke = new SingleLinkedList();
}
//添加元素
public void push(Object data) {
linke.addHead(data);
}
//移除栈顶元素
public Object pop() {
Object obj = linke.deleteHead();
return obj;
}
//判断是否为空
public boolean isEmpty() {
return linke.isEmpty();
}
//打印栈内元素信息
public void disply() {
linke.display();
}
}
测试：
public class TestSingleLinkedList {
@Test
public void testSingleLinkedList() {
SingleLinkedList singleLinkeList = new SingleLinkedList();
singleLinkeList.addHead("A");
singleLinkeList.addHead("B");
singleLinkeList.addHead("C");
singleLinkeList.addHead("D");
//打印当前列表信息
singleLinkeList.display();
//删除节点C
singleLinkeList.delete("C");
singleLinkeList.display();
//查找B
System.out.println(singleLinkeList.find("B"));
System.out.println(singleLinkeList.isEmpty());
singleLinkeList.deleteHead();
singleLinkeList.display();
}
}
结果：
[D->C->B->A]
[D->B->A]
practice.com.wzy.singlelinke.SingleLinkedList$Node@4459eb14
false
[B->A]