1、单向链表
单向链表的特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部开始;链表是使用指针进行构造的列表;又称为结点列表,因为链表是由一个个结点组装起来的;其中每个结点都有指针成员变量指向列表中的下一个结点。
public class Node {
Object value;
Node next;
public Node(String value){
this.value = value;
}
}
public class LinkedListTest {
Node first;
Node last;
public void add(Node node){
if(first == null){
first = node;
last = node;
}else{
last.next = node;
last = node;
}
}
public Node getFirstNode(){
return first;
}
public Node getLastNode(){
return last;
}
public int getSize(){
int size = 0;
Node node = first;
while(node != null){
size ++;
node = node.next;
}
return size;
}
public static void main(String[] args) {
LinkedListTest link = new LinkedListTest();
Node node1 = new Node("node1");
Node node2 = new Node("node2");
Node node3 = new Node("node3");
link.add(node1);
link.add(node2);
link.add(node3);
System.out.println(link.getSize());
System.out.println(link.getFirstNode().value);
System.out.println(link.getLastNode().value);
}
}
2、双向链表
双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
public class DoublyNode {
Object value;
DoublyNode next;
DoublyNode pre;
public DoublyNode(String value){
this.value = value;
}
}
public class DoublyLinkedListTest {
DoublyNode first;
DoublyNode last;
public void add(DoublyNode node){
if(first == null){
first = node;
last = node;
}else{
last.next = node;
node.pre = last;
last = node;
last.next = first;
first.pre = last;
}
}
public Object remove(Object val) throws Exception{
if(first == null)
throw new Exception("empty!");
DoublyNode cur = first;
while(cur != null){
if(cur.value.equals(val)){
if(cur == last)
last = cur.pre;
else
cur.next.pre = cur.pre;
if(cur == first)
first = cur.next;
else
cur.pre.next = cur.next;
return val;
}
cur = cur.next;
}
return null;
}
public int getSize(){
int size = 0;
DoublyNode node = first;
while(node != null){
size ++;
if(node.next == first){
node = null;
}else{
node = node.next;
}
}
return size;
}
public static void main(String[] args) throws Exception {
DoublyLinkedListTest link = new DoublyLinkedListTest();
DoublyNode node1 = new DoublyNode("node1");
DoublyNode node2 = new DoublyNode("node2");
DoublyNode node3 = new DoublyNode("node3");
link.add(node1);
link.add(node2);
link.add(node3);
System.out.println(link.remove("node2"));
System.out.println(link.getSize());
}
}
今天的文章Java实现单向链表和双向链表分享到此就结束了,感谢您的阅读,如果确实帮到您,您可以动动手指转发给其他人。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/27232.html