内部类实现单向链表

内部类 Node 实现单链表


题:单链表的实现_完善方案
我们在示例中给出的链表类是递归定义的。这样做的好处是链表的某个局部也是一个链表,这与链表在逻辑上的概念具有一致性。

但出于效率的考虑,经常需要引入一些辅助变量来加快操作的速度,这时,如果能给链表类型增加一个外壳就很方便后续的处理。

基本思路:

class MyList
{
private Node head;

class Node{
int data;
Node next;
}

....
}

这种方案中,MyList不是递归定义的,而内部包含的Node类代表了链表的真实结构。MyList类是一个外壳类。它通过持有head 指针来记录一个链表的头在哪里。

请试着完善这种方案。

源码SLList.java


package SLList;

public class SLList {
    
    private Node head;
    
    public void add(int x) {
        Node p = new Node(x);
        if (this.head==null) {
            this.head = p;
        }
        else {
            this.head.addNode(p);
        }
    }
    public boolean src(int x) {
        if (head!=null) {
            return this.head.searchNode(x);
        }
        else {
            return false;
        }
    }
    public void del(int x) {
        if (this.src(x)) {
            this.head.deleteNode(head, x);
        }
    }
    public void show() {
        if (this.head!=null) {
            this.head.showNode();
        }
    }
    
    // Inner class
    class Node {
        private int data;
        private Node next;
        public Node(int x) {
            this.data = x;
            this.next = null;
        }
        public int getData() {
            return this.data;
        }
        public void setNext(Node x) {
            this.next = x;
        }
        public void addNode(Node x) {
            Node p = this;
            while (p.next!=null) {
                p = p.next;
            }
            p.next = x;
        }
        public void showNode() {
            Node p = this;
            while (p!=null) {
                System.out.println(p.data);
                p = p.next;
            }
        }
        public boolean searchNode(int x) {
            Node p = this;
            if(p.data==x) {
                return true;
            }
            else {
                if (p.next!=null) {
                    return p.next.searchNode(x);
                }
                else {
                    return false;
                }
            }
        }
        public void deleteNode(Node f, int x) {
            Node p = this;
            if(p.data==x) {
                if(p.next!=null) {
                    f.next = p.next;
                }
                else {
                    f = null;
                }
            }
            else {
                if(p.next!=null) {
                    p.next.deleteNode(p, x);
                }
            }
        }
    }
}

参考——ITEYE

发表评论

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