Java实现单向链表和双向链表

Java实现单向链表和双向链表1、单向链表单向链表的特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部开始;链表是使用指针进行构造的列表;又称为结点列表,因为链表是由一个个结点组装起来的;其中每个结点都有指针成员变量指向列表中的下一个结点。publicclassNode{Objectvalue;Nodenext;publicNode(Stringvalue){

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

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注