A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© EscapedPupil 初级黑马   /  2019-6-6 12:41  /  710 人查看  /  0 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

近日,在学Java的途中,琢磨着单链表的实现应该是由节点元素和链体构成。
        那么就应该可以按照链体封装节点为内部类的方法来实现单链表。
        public class LinkList(){
                //链体
                private class Link(){
                        //节点
                }
        }
        节点类属性:需要有一个头结点(first),需要有节点存储的数据(data),
        需要有当前节点指向下一节点的标识(next)。
        链表的思路:first值为第一个节点地址Link first = new Link(data);
        第二个节点:first.next = new Link(data);
        第三个节点:first.next.next = new Link(data)...以此类推。
        每个单链表只会有一个表头,则LinkList中成员属性仅需要添加Link first。
        public class LinkList{
                private Link first;
                public LinkList(){
                        this.first = null ;//first作为成员本身值也是null,这里只是注明:
                        //链表创建,生成空节点对象。
                }
                private class Link{
                        public Link first;//first在此处虽然没有使用static修饰,但在链表中效果类似
                        public Link next;
                        public int data;
                        public Link(int data){
                                this.data = data;
                        }
                }
        单链表原始设计,差不多就这样。
        但我们想要用其增删改元素,还需定义方法。
        以下是重点,也是个人觉得的链表易错点。
        public boolean isEmpty() {
            return this.first == null;        //判断链表是否为空。
        }
        private void addFirst(int data) {
            this.first = new Link(data);  //私有化添加第一个元素,可以并入*******处
        }
        public boolean add(int data) {
        if (this.isEmpty()) {
            this.addFirst(data);                        //********
        }
        else {
            Link temp = this.first;
            while (temp.next != null) {    //链表着重注意点:1(个人理解):
                     temp = temp.next;
            }
            temp.next = new Link(data);                 ////链表着重注意点:2(个人理解)
        }
       return true;
   }
   注意点1:判断temp指向的节点的next是否指向空,
   为空代表temp指向的节点的下一个节点不存在,可以添加。
   注意2:这里与注意点1对比,不能用temp!=null来充当while循环的判断条件。
   虽然temp是充当临时变量,指向每一个节点,
   但如果temp指向了空, 那么temp = new Link(data),
   仅仅是给temp赋值。并没有添加到链体里。
   可以自行测试
                           while (temp != null) {    //链表着重注意点:1(个人理解):
                     temp = temp.next;
            }
            temp = new Link(data);                 ////链表着重注意点:2(个人理解)
   其他方法比较好理解,就不一一赘述。如果要实现索引功能,
   需要额外在Link节点添加成员index。
   以下是实现了几个小功能的单链表代码:
public class LinkList<T> {
        //私有化Link节点的头结点
        //每个LinkList创建之初,都会自动生成一个null值的头结点
            private Link first;
       
            public LinkList() {
                this.first = null;
            }
       
            private void addFirst(T data) {
                this.first = new Link(data);
                ensureIndex();
            }
       
            //判断是否为空
            public boolean isEmpty() {
                return this.first == null;
            }
       
            //添加。
            public boolean add(T data) {
                if (this.isEmpty()) {
                    this.addFirst(data);
                } else {
                    Link temp = this.first;
                    while (temp.next != null) {
                        temp = temp.next;
                    }
                    temp.next = new Link(data);
                    ensureIndex();
                }
                return true;
            }
       
            //遍历
            public void show() {
                Link temp = this.first;
                System.out.print("[");
                while (temp != null) {
                    if (temp.next != null) {
                        System.out.print(temp.data + ",");
                    } else {
                        System.out.print(temp.data);
                    }
                    temp = temp.next;//this.first.next = current = new Link(23) != null
                }
                System.out.println("]");
            }
       
       
            //select from index
            public T getByIndex(int index) {
                Link temp = this.first;
                for (int i = 0; i < index; i++) {
                    temp = temp.next;
                    if (temp == null) {
                        throw new IndexOutOfBoundsException("不正确的索引");
                    }
                }
                return (T) temp.data;
            }
       
            //修改元素:通过比较存储值是否equals,
            public boolean replace(T data, T dataNew) {
                Link temp = this.first;
                while (true) {
                    if (temp == null) {
                        return false;
                    }
                    if (!(temp.data.equals(data))) {
                        temp = temp.next;
                    } else {
                        temp.data = dataNew;
                        return true;
                    }
                }
            }
       
            //删除某个元素
            public boolean remove(T data) {
                if (this.first == null) {
                    return false;
                }
                Link temp = this.first;
                if (temp.data.equals(data)) {
                    this.first = temp.next;
                    return true;
                }
                while (true) {
                    if (temp.next == null) {
                        return false;
                    }
                    if (!temp.next.data.equals(data)) {
                        temp = temp.next;
                    } else {
                        temp.next = temp.next.next;
                        ensureIndex();
                    }
                }
            }
            //确定元素对应索引值。
            private void ensureIndex() {
                Link temp = this.first;
                if (temp.index != 0) {
                    temp.index = 0;
                }
                while (temp.next != null) {
                    if (temp.next.index != temp.index + 1) {
                        temp.next.index = temp.index + 1;
                        temp = temp.next;
                    } else {
                        temp = temp.next;
                    }
                }
            }
       
            private class Link<T> {
                public T data;
                public Link next;
                public Link first;
       
                public Link(T data) {
                    this.data = data;
                }
       
                public int index;
                    }
}
---------------------

0 个回复

您需要登录后才可以回帖 登录 | 加入黑马