数据结构和算法-009 双向链表

梦里梦外; 2022-01-11 08:33 229阅读 0赞

双向链表，就是在一个节点（node）有两个指针（point），分别指向前一个节点和后一个节点，它和链表最大的区别就是，链表是单向的，只能找到后面的节点，不能往前找，双向链表顾名思义，双向的，可以往后找，也可以往前。

这段代码有点复杂，先看看，再一点点解释吧

public class DoubleLinkList {
        
        Neighbor firstLink;
        Neighbor lastLink;
        
        public void insertFirstPosition(String ownerName, int houseNumber){
            Neighbor newLink = new Neighbor(ownerName, houseNumber);
            if(isEmpty()){
                lastLink = newLink;
            } else {
                firstLink.previous= newLink;
            }
            newLink.next= firstLink;
            firstLink = newLink;
            
        }
        
        public void insertLastPosition(String ownerName, int houseNumber){
            Neighbor newLink = new Neighbor(ownerName, houseNumber);
            if(isEmpty()){
                firstLink = newLink;
            } else {
            
                lastLink.next= newLink;
                newLink.previous= lastLink;
            }
            lastLink = newLink;
            
        }
        
        
        public void insertInOrder(String ownerName, int houseNumber){
            Neighbor newLink = new Neighbor(ownerName, houseNumber);
            
            Neighbor previousLink= null;
            Neighbor currentLink = firstLink;
            
            while (currentLink!= null && houseNumber>currentLink.houseNumber){
                previousLink =currentLink;
                currentLink = currentLink.next;
            }
            
            
            
            if(previousLink == null){
                firstLink = newLink;
            }else{
                previousLink.next= newLink;
            }
            
            newLink.next = currentLink;
        }
        
        
        public boolean insertAfterKey(String ownerName, int houseNumber, int key){
            Neighbor newLink = new Neighbor(ownerName, houseNumber);
            
            Neighbor currentLink = firstLink;
            
            while (currentLink.houseNumber != key){
                currentLink = currentLink.next;
                if(currentLink== null){
                    return false;
                }
            }
            
            if(currentLink == lastLink){
                newLink.next= null;
                lastLink = newLink;
            }else{
                newLink.next= currentLink.next;
                currentLink.next.previous = newLink;
            }
            newLink.previous=currentLink;
            currentLink.next= newLink;
            return true;
        }
        
        
        public boolean isEmpty(){
            return firstLink == null && lastLink == null;
        }
        
    
        public void display(){
            Neighbor theLink =firstLink;
            
            while (theLink != null){
                theLink.printNerghbor();
                System.out.println("Next Link: " + theLink.next);
                theLink= theLink.next;
            }
        }
        
        public static void main(String[] args) {
            System.out.println("Create a DoubleLinkList");
            DoubleLinkList linkedList = new DoubleLinkList();
            System.out.println();
            
            System.out.println("Add First Node at fitst position");
            linkedList.insertFirstPosition("Lucio", 7);
            linkedList.display();
            System.out.println();
            
            System.out.println("Add Second Node at fitst position");
            linkedList.insertFirstPosition("Matt", 6);
            linkedList.display();
            System.out.println();
            
            System.out.println("Add Third Node at last position");
            linkedList.insertLastPosition("Leo", 500);
            linkedList.display();
            System.out.println();
            
            System.out.println("Add Fouth Node at last position");
            linkedList.insertLastPosition("Angela", 501);
            linkedList.display();
            System.out.println();
            
            System.out.println("Add a Node in order house number");
            linkedList.insertInOrder("Jack", 143);
            linkedList.display();
            System.out.println();
            
            System.out.println("Add another two Nodes in order house number");
            linkedList.insertInOrder("James", 122);
            linkedList.insertInOrder("Renee", 155);
            linkedList.display();
            System.out.println();
            
            System.out.println("Add a Nodes after special house number");
            linkedList.insertAfterKey("Jason", 123, 143);    
            linkedList.display();
            System.out.println();
            
            System.out.println("Create Iterator for DoubleLinkList");
            NeighborIterator neighbors = new NeighborIterator(linkedList);
            System.out.println();
            
            System.out.println("Print current Node in the Linklist");
            neighbors.currentLink.printNerghbor();
            System.out.println();
            
            System.out.println("Current Node has next None: " + neighbors.hasNext());
            System.out.println();
            
            System.out.println("Go to next 2 node");
            neighbors.next();
            neighbors.next();        
            System.out.println();
            
            System.out.println("Print current Node in the Linklist");
            neighbors.currentLink.printNerghbor();
            System.out.println();
            
            System.out.println("Print next node");
            neighbors.next().printNerghbor();
            System.out.println();
            
            System.out.println("Print current Node in the Linklist");
            neighbors.currentLink.printNerghbor();
            System.out.println();
            
            System.out.println("Remove Current Node");
            neighbors.remove();
            System.out.println();
            linkedList.display();
                    
        }
    }
    
    class NeighborIterator{
        
        Neighbor currentLink;
        Neighbor previousLink;
        
        DoubleLinkList linkList;
        
        NeighborIterator(DoubleLinkList linkList){
            this.linkList = linkList;
            currentLink = linkList.firstLink;
            previousLink = linkList.lastLink;        
        }
        
        public boolean hasNext(){
            if(currentLink.next != null){
                return true;
            }
            return false;
        }
        
        public Neighbor next(){
            if(hasNext()){
                previousLink= currentLink;
                currentLink = currentLink.next;
                return currentLink;
            }
            return null;
        }
        
        public void remove(){
            if(previousLink == null){
                linkList.firstLink= currentLink.next;
            } else {
                previousLink.next = currentLink.next;
                if(currentLink.next == null){
                    currentLink =linkList.firstLink;
                    previousLink = null;
                } else {
                    currentLink = currentLink.next;    
                    currentLink.previous=previousLink;
                }
            }
        }
    }
    
    
    class Neighbor{
        
        public String ownerName;    
        public int houseNumber;
        
        public Neighbor next;
        public Neighbor previous;
        
        
        Neighbor(String ownerName, int houseNumber){
            this.ownerName = ownerName;        
            this.houseNumber = houseNumber;
        }
        
        public void printNerghbor(){
            System.out.println(ownerName + ": " + houseNumber);
        }
        
        public String toString(){
            return this.ownerName;
        }
        
    }

Neighbor 就是节点（Node），可以看到两个引用，一个指向前一个节点（previous），一个指向后一个(next)。

public Neighbor next;
    public Neighbor previous;

其他的自己看了

DoubleLinkList 就是双向链表

两个引用指向起始和结尾的节点，

Neighbor firstLink;
    Neighbor lastLink;

解释以下头部插入的方法

public void insertFirstPosition(String ownerName, int houseNumber){
            // 创建一个节点
            Neighbor newLink = new Neighbor(ownerName, houseNumber);
            // 如过链表为空
            if(isEmpty()){
                // 把新节点设为最后一个节点
                lastLink = newLink;
            } else {//链表不为空
                // 把新节点设为第一个节点之前的节点
                firstLink.previous= newLink;
            }
            // 新节点的后的节点设为当前第一个节点
            newLink.next= firstLink;
            // 把新节点设为第一个节点
            firstLink = newLink;      
        }

不知道看懂没有，简单说就是把新节点放在最前面，然后调整引用，在第一个节点设为新节点。

后面一个方法不解释了，意思差不多。

NeihbourIterator 是一个简单的Iterator，实现了hasNext() 和next()方法

通过两个引用实现控制

Neighbor currentLink;
    Neighbor previousLink;

remove（删除）的方法写NeighborIterator类中是因为DoubleLinkedList类过于简单，无法获得当前节点。正好Iterator可以获得。在Java.util中的LindedList带有remove方法，但是是和索引一起使用的。

输出结果

Create a DoubleLinkList
    
    Add First Node at fitst position
    Lucio: 7
    Next Link: null
    
    Add Second Node at fitst position
    Matt: 6
    Next Link: Lucio
    Lucio: 7
    Next Link: null
    
    Add Third Node at last position
    Matt: 6
    Next Link: Lucio
    Lucio: 7
    Next Link: Leo
    Leo: 500
    Next Link: null
    
    Add Fouth Node at last position
    Matt: 6
    Next Link: Lucio
    Lucio: 7
    Next Link: Leo
    Leo: 500
    Next Link: Angela
    Angela: 501
    Next Link: null
    
    Add a Node in order house number
    Matt: 6
    Next Link: Lucio
    Lucio: 7
    Next Link: Jack
    Jack: 143
    Next Link: Leo
    Leo: 500
    Next Link: Angela
    Angela: 501
    Next Link: null
    
    Add another two Nodes in order house number
    Matt: 6
    Next Link: Lucio
    Lucio: 7
    Next Link: James
    James: 122
    Next Link: Jack
    Jack: 143
    Next Link: Renee
    Renee: 155
    Next Link: Leo
    Leo: 500
    Next Link: Angela
    Angela: 501
    Next Link: null
    
    Add a Nodes after special house number
    Matt: 6
    Next Link: Lucio
    Lucio: 7
    Next Link: James
    James: 122
    Next Link: Jack
    Jack: 143
    Next Link: Jason
    Jason: 123
    Next Link: Renee
    Renee: 155
    Next Link: Leo
    Leo: 500
    Next Link: Angela
    Angela: 501
    Next Link: null
    
    Create Iterator for DoubleLinkList
    
    Print current Node in the Linklist
    Matt: 6
    
    Current Node has next None: true
    
    Go to next 2 node
    
    Print current Node in the Linklist
    James: 122
    
    Print next node
    Jack: 143
    
    Print current Node in the Linklist
    Jack: 143
    
    Remove Current Node
    
    Matt: 6
    Next Link: Lucio
    Lucio: 7
    Next Link: James
    James: 122
    Next Link: Jason
    Jason: 123
    Next Link: Renee
    Renee: 155
    Next Link: Leo
    Leo: 500
    Next Link: Angela
    Angela: 501
    Next Link: null

转载于:https://blog.51cto.com/10324466/1663418