双向链表的学习和实现

1：双向链表的概念和优缺点

 

• 概念

　　　　每一个node都包含指向下一个node的引用Next，以及指向前一个node的Pre。这样说就可以双向的遍历链表！不想单向列表只能从前往后的遍历。

 

• 优缺点

 

　　1：支持双向查找，相比而言更快，但是每个节点多了，一个指向前节点的引用。

　　2：不需要temp节点缓存当前节点的前节点，而只通过本节点就可以方访问前后，实现增和删！　

 

 

2：双向链表的增，删，改的Java实现

• 增

　　　　思路分析：先通过遍历的方式找到当前链表的为节点，然后插入。其中主要双向链表不需要temp就可以完成增删的操作！！

    //在链表尾部增加节点
    public void addNodeInEnd(HeroNode node) {
        HeroNode curNode = head;//用来遍历链表的引用变量，从head开始
        //遍历链表，直到当前节点的next为null，这时找到了本链表的尾节点。
        while(curNode.getNext()!=null) {
            
            curNode = curNode.getNext();
        }
        //curNode的next指向node
        curNode.setNext(node);
        //node的pre指向curNode
        node.setPre(curNode);
    }

 

 

• 删

• 改

• 代码演示

package TwoDirectionList;

public class TwoDirectionListTest {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        //创建节点
        HeroNode head = new HeroNode(0,"head");
        HeroNode h1 = new HeroNode(1,"张飞");
        HeroNode h2 = new HeroNode(2,"赵云");
        HeroNode h3 = new HeroNode(3,"刘备");
        HeroNode h4 = new HeroNode(4,"曹操");
        //创建列表
        TwoDirectionList tdl = new TwoDirectionList(head);
        tdl.addNodeInEnd(h1);
        tdl.addNodeInEnd(h2);
        tdl.addNodeInEnd(h3);
        tdl.addNodeInEnd(h4);
        //显示列表
        tdl.showNode();
        System.out.println("***********删除节点**********");
        //删除节点
        tdl.delNode(h1);
        tdl.delNode(h4);
        
        //显示列表
        tdl.showNode();
        
        System.out.println("***********查找节点**********");
        System.out.println(tdl.findNode(h2)); 
        System.out.println(tdl.findNode(h3)); 
        
        System.out.println("***********修改节点**********");
        tdl.changeNode(h2,new HeroNode(1,"猪猪")); 
        tdl.changeNode(h3,new HeroNode(1,"驴驴")); 
        //显示列表
        tdl.showNode();

    }

}


class TwoDirectionList{
    private HeroNode head = null;//头节点

    public TwoDirectionList(HeroNode head) {
        super();
        this.head = head;
    }
    
    //在链表尾部增加节点
    public void addNodeInEnd(HeroNode node) {
        HeroNode curNode = head;//用来遍历链表的引用变量，从head开始
        //遍历链表，直到当前节点的next为null，这时找到了本链表的尾节点。
        while(curNode.getNext()!=null) {
            
            curNode = curNode.getNext();
        }
        //curNode的next指向node
        curNode.setNext(node);
        //node的pre指向curNode
        node.setPre(curNode);
    }
    
    

    //在链表指定位置增加节点
    public int addNodeWithOrder(HeroNode node) {
    
        return 1;
    }

    //删除指定节点，按照节点内容进行删除
    public void delNode(HeroNode node) {
        HeroNode curNode = head;
        while(true) {
            if(curNode.getName()==node.getName()) {//双向链表的删除操作不需要temp来指向该节点的前节点，而直接使用该节点的Pre即可!
                if(curNode.getNext() == null) {
                    //加入待删除的是最后一个节点
                    curNode.getPre().setNext(null);
                    curNode.setPre(null);
                    break;
                }
                else {
                //删除操作,先将该节点的前节点的next指向该节点的next
                curNode.getPre().setNext(curNode.getNext());
                //将改节点的后节点的pre指向该节点前节点
                curNode.getNext().setPre(curNode.getPre());
                break;
                }
            }
            if(curNode == null) {
                System.out.println("没有找到该节点！");
                break;
            }
            curNode = curNode.getNext();
        }
        
        
    }
    
    //找到指定节点，返回指向该节点为引用
    public HeroNode findNode(HeroNode node) {
        HeroNode curNode = head;
        while(true) {
            if(curNode.getName()==node.getName()) {
                return curNode;
            }
            if(curNode == null) {
                System.out.println("没有找到该节点！");
                return null;
            }
            curNode = curNode.getNext();
        }
    }
    
    //修改节点内容，根据源节点和修改节点
    public void changeNode(HeroNode objectNode,HeroNode node) {
        HeroNode objectNodeResult = findNode(objectNode);
        if(objectNodeResult == null) {
            return ;
        }
        else {
            objectNodeResult.setName(node.getName());
        }
    }
    
    //打印链表内容
    public void showNode() {
        HeroNode curNode = head;
        while(curNode!= null) {
            System.out.println(curNode);
            curNode = curNode.getNext();
            }
    }
}



class HeroNode{
    private int num = 0;
    private String name = null;
    private  HeroNode pre = null;
    private HeroNode next = null;
    
    //构造方法
    public HeroNode(int num, String name) {
        super();
        this.num = num;
        this.name = name;
    }
    
    //getter和setter
    public int getNum() {
        return num;
    }
    public String getName() {
        return name;
    }
    public HeroNode getPre() {
        return pre;
    }
    public HeroNode getNext() {
        return next;
    }
    public void setNum(int num) {
        this.num = num;
    }
    public void setName(String name) {
        this.name = name;
    }
    public void setPre(HeroNode pre) {
        this.pre = pre;
    }
    public void setNext(HeroNode next) {
        this.next = next;
    }

    //toString
    @Override
    public String toString() {
        return "HeroNode [num="   num   ", name="   name   "]";
    }
    

    
}