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

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

LinkedList代码底层就是利用了双向链表。
我尝试着自己写了一个,是跟着课程边学边写的。所以有些功能写的不好,比如get(index)方法和remove(index)方法没判它的长度是否该从尾部查起,
getfirst和getlast等功能也还没加入,等有空我完善了再和大家分享一次。
//----------------------链表的实现代码如下---------------------------
/要实现的内容
//1,前后节点
//2,size
//3,首尾地址属性
//4,单参的延生链表
//5,search,replace,delete,
//6,
public class Node<E> {
        //private int num;                                //
        private int size;                                //链表长度
        private Node<E> firstNode;                                //首节点
        private Node<E> lastNode;                                //末节点
       
        private Node<E> nextNode = null;                //后节点
        private Node<E> preNode = null;                //前节点
        private E /*Object*/ obj;                                        //存储的内容
       

        public Node() {
                super();
                size = 0;
                firstNode = this;
        }
       
        public Node(E anobject) {
                super();
                //Node newNode = new Node();
                this.obj = anobject;
        }
       
        public int size(){
                return size;
        }
       
        //实现,在链表末尾插入新值,注意表头为this.nextNode,this为调用对象其索引为-1
/*        public boolean add(Object anobject){
                Node newNode =new Node(anobject);
                incNode(this,newNode);//这段需要重写已过时。可用
                size++;
                if(firstNode == null)
                        firstNode = newNode;
                lastNode = newNode;
                return true;
        }*/
       
//测试firstNode和lastNode用代码,需删除
        public Object getFirst(){
                return firstNode.obj;
        }
        public Object getlast(){
                return lastNode.obj;
        }
//测试已通过,可删除       
       
        //根据聊表尾地址增长链表
        public boolean add(E anobject){
                Node<E> newNode =new Node<E>(anobject);
                incNode(this,newNode);
                if(size == 0){
                        firstNode = newNode;
                        lastNode = newNode;
                        this.nextNode = newNode;
                        newNode.preNode = this;
                }
                else{
                        lastNode.nextNode = newNode;
                        newNode.preNode = lastNode;
                        lastNode = newNode;
                }
                size++;
                return true;
        }
        //实现,在指定位置插入对象功能
        public boolean add(int index,E anobject){
                if(index > size &&index <0)
                        return false;
                Node<E> newNode =new Node<E>(anobject);
                if(size == 0){
                        firstNode = newNode;
                        lastNode = newNode;
                        this.nextNode = newNode;
                        newNode.preNode = this;
                }
                if(index == 0)
                        firstNode = newNode;
                if(index == size)
                        lastNode = newNode;
                Node<E> targetNode = searchIndex(index,this);//从对象名后面开始插值,此时获得的目标为索引-1
                if(targetNode.nextNode != null ){
                        newNode.preNode = targetNode;
                        newNode.nextNode = targetNode.nextNode;
                        targetNode.nextNode = newNode;
                        newNode.nextNode.preNode = newNode;
                }else{
                        newNode.preNode = targetNode;
                        //newNode.nextNode = targetNode.nextNode;//null=null,所以此句无用
                        targetNode.nextNode = newNode;
                }
                size++;
                return true;
        }
       
        //已实现,删除指定索引的链表节点
        public boolean remove(int index){
                if(index >= size && index <0)
                        return false;
                size--;
                if(index == 0)
                        firstNode = firstNode.nextNode;
                if(index == size)
                        lastNode = lastNode.preNode;
                //此时不可能取到索引末尾,取得的最后地址为(索引-1),targetNode_1为目标节点前一个节点
                Node<E> targetNode_1 = searchIndex(index,this);
                if(targetNode_1.nextNode.nextNode != null){
                        targetNode_1.nextNode.nextNode.preNode = targetNode_1;
                        targetNode_1.nextNode = targetNode_1.nextNode.nextNode;
//                        Node tempNode = targetNode_1.nextNode.nextNode;
//                        targetNode_1.nextNode = tempNode;
                        return true;
                }else{
                        targetNode_1.nextNode = null;
                        return true;
                }
        }
        //已实现,删除指定元素的链表节点,调用toString属性判断二者是否相等,正确删除返回true,找不到返回false
        public boolean remove(E anobject){
                Node<E> targetNode = searchObject(anobject,this.nextNode);
                if(targetNode == null){
                        return false;
                }else if(targetNode.nextNode == null){
                        targetNode.preNode.nextNode = null;
                        lastNode = targetNode.preNode;
                        return true;
                }else{
                        if(targetNode == firstNode)
                                firstNode = targetNode.nextNode;
                        targetNode.nextNode.preNode = targetNode.preNode;
                        targetNode.preNode.nextNode = targetNode.nextNode;
                        return true;
                }
        }
       
        //已实现,返回指定索引的Object属性
        public E get(int index){
                //若是索引越界,返回null
                if(index >= size && index <0)
                        return null;
                Node<E> targetNode = searchIndex(index,this.nextNode);
                return targetNode.obj;
        }
        //由于toString方法已经重写,所以该方法可以放弃,但其显示效率比toString高
        public void show(){
                if(this.nextNode == null)
                        return;
                System.out.print("[");
                showNode(this.nextNode);
        }
       
        @Override
        public String toString() {
                if(this.nextNode == null)
                        return null;
                String str = new String();
                str += "[";
                str = nodeToString(this.nextNode,str);
                return str;
        }

        //--------------------------------------       
        //在x1最后新插入Node,延长链表,靠add方法调用
        private void incNode(Node<E> x1,Node<E> x2)
        {
                if(x1.nextNode == null)
                {
                        x2.nextNode = null;
                        x2.preNode = x1;
                        x1.nextNode = x2;
                }else
                {
                        incNode(x1.nextNode,x2);       
                }
        }
       
        //已实现,递归寻找指定索引的地址
        private Node<E> searchIndex(int index,Node<E> nowNode){
                Node<E> returnNode = null;
                if (index == 0){
                        return (returnNode = nowNode);
                }
                else {
                        index--;
                        returnNode = searchIndex(index,nowNode.nextNode);
                }
                return returnNode;       
        }
        //未实现,重复功能函数,放弃使用
/*        private  void nodeInsert(int index,Node newNode){
                Node returnNode = null;
                if (index ==0){
                        return (returnNode = nowNode);
                }
                else {
                        index--;
                        returnNode = searchNode(index,nowNode.nextNode);
                }
                return returnNode;
        }*/
        private Node<E> searchObject(E tarObject,Node<E> nowNode){
                Node<E> targetNode = null;
                if(tarObject.equals(nowNode.obj)){
                        return nowNode;
                }else if(nowNode.nextNode == null){
                        return null;
                }else{
                        targetNode = searchObject(tarObject,nowNode.nextNode);
                }
                return targetNode;
        }


//遍历显示链表的所有属性
        private void showNode(Node<E> nowNode)
        {
                System.out.print(nowNode.obj.toString());
                if(nowNode.nextNode == null)
                {
                        System.out.println("]");
                }else
                {       
                        System.out.print(",");
                        showNode(nowNode.nextNode);
                }
        }
        private String nodeToString(Node<E> nowNode, String str) {
                String str1=str + nowNode.obj.toString();
                if(nowNode.nextNode == null)
                {
                        str1 += "]";
                }else
                {       
                        str1 += ",";
                        str1 = nodeToString(nowNode.nextNode,str1);
                }
                return str1;
        }
}


//------------下面是主程序里的演示模块,其实用起来和系统自带的LinkedList一样啦。当然功能没他那么强大,不过泛型之类的已经实现了。有建议的可以联系我,我学习空隙改下,谢谢。
public static void main(String[] args) {
                /*
                 *         Node的add、add带索引、remove索引、remove指定object、get函数、size函数、以及
                          显示结果函数均已经实现*/
                Node c = new Node();//Linklist c = new Linklist();
                c.add("a");
                c.add("b");
                c.add("c");
                c.add("123");
                //将"23"插在0位置
                c.add(0, "23");
                c.add(5,100);
                c.add(5,101);
                //删除第一个以及最后一个元素
                c.remove(0);
                c.remove(c.size()-1);
                //新建学生类对象
                c.add(new Student());
                //删除"23"元素
                c.remove("23");       
                //已实现toString,c.show方法可以隐藏
                c.show();
                System.out.println(c);
                System.out.println(c.get(2).toString());

//-----------------------------------------------------------
源码的java文件我已经发在附件里了,方便大家测试使用

node2.rar

3.29 KB, 下载次数: 47

评分

参与人数 1技术分 +1 收起 理由
洋葱头头 + 1

查看全部评分

10 个回复

倒序浏览
人生第二贴。大大们轻拍
回复 使用道具 举报
yubail 来自手机 中级黑马 2015-11-24 22:33:38
藤椅
我又来顶你了
回复 使用道具 举报
总结的很好  写的很详细  赞
回复 使用道具 举报
wunaihaoye 来自手机 中级黑马 2015-11-24 23:03:34
报纸
赞一个
回复 使用道具 举报
大神就是大神啊,总结的不错,写的不错啊
回复 使用道具 举报
hhl 中级黑马 2015-11-24 23:07:28
7#
大神,技术好屌,期待更新
回复 使用道具 举报
大神
回复 使用道具 举报
好厉害啊啊啊啊啊啊啊
回复 使用道具 举报
屌,为楼主的勤奋细致点赞
回复 使用道具 举报
棒棒棒   你已经比我学得好了
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马