Java - Doubly Linked List

環狀雙向鏈結串列

001:  import java.util.List;  
002:  import java.util.ArrayList;  
003:    
004:  class dllNode{  
005:       Object objNodeField; //節點屬性  
006:       dllNode dlnPre, dlnNext;  
007:         
008:       dllNode(){ }  
009:       dllNode(Object obj){  
010:            objNodeField = obj;  
011:       }  
012:  }  
013:    
014:  class DoublyLinkedList {  
015:       dllNode dlnHead;  
016:         
017:       DoublyLinkedList(){  
018:            dlnHead = new dllNode();  
019:            dlnHead.dlnPre = dlnHead;  
020:            dlnHead.dlnNext = dlnHead;  
021:       }  
022:         
023:       boolean IsEmpty(){  
024:            if(dlnHead.dlnNext==dlnHead)  
025:                 return true;  
026:            return false;  
027:       }  
028:         
029:       void Append(Object objNodeField){ //加入資料到尾端  
030:            dllNode dlnNew = new dllNode(objNodeField);  
031:            dlnNew.dlnNext = dlnHead;  
032:            dlnNew.dlnPre = dlnHead.dlnPre;  
033:            dlnHead.dlnPre = dlnNew;  
034:            dlnNew.dlnPre.dlnNext = dlnNew;   
035:       }       
036:       void AddTop(Object objNodeField){ //加入資料到前端  
037:            dllNode dlnNew = new dllNode(objNodeField);  
038:            dlnNew.dlnNext = dlnHead.dlnNext;  
039:            dlnNew.dlnPre = dlnHead;  
040:            dlnHead.dlnNext = dlnNew;  
041:            dlnNew.dlnNext.dlnPre = dlnNew;   
042:       }  
043:         
044:       Object Top(){ //傳回前端資料  
045:            return dlnHead.dlnNext.objNodeField;  
046:       }  
047:       Object End(){ //傳回尾端資料  
048:            return dlnHead.dlnPre.objNodeField;  
049:       }  
050:         
051:       Object PopTop(){ //彈出前端資料  
052:            if(IsEmpty())  
053:                 return null;  
054:            dllNode dlnTop = dlnHead.dlnNext;  
055:            Object objTopField = dlnTop.objNodeField;  
056:            dlnTop.dlnPre.dlnNext= dlnTop.dlnNext;  
057:            dlnTop.dlnNext.dlnPre = dlnTop.dlnPre;  
058:            dlnTop.dlnPre = null;  
059:            dlnTop.dlnNext = null;  
060:            dlnTop.objNodeField = null;  
061:            dlnTop = null;  
062:            return objTopField;  
063:       }  
064:       Object PopEnd(){ //彈出尾端資料  
065:            if(IsEmpty())  
066:                 return null;  
067:            dllNode dlnEnd = dlnHead.dlnPre;  
068:            Object objTopField = dlnEnd.objNodeField;  
069:            dlnEnd.dlnPre.dlnNext= dlnEnd.dlnNext;  
070:            dlnEnd.dlnNext.dlnPre = dlnEnd.dlnPre;  
071:            dlnEnd.dlnPre = null;  
072:            dlnEnd.dlnNext = null;  
073:            dlnEnd.objNodeField = null;  
074:            dlnEnd = null;  
075:            return objTopField;  
076:       }  
077:         
078:       boolean RemoveTop(){ //移除前端節點  
079:            if(IsEmpty())  
080:                 return false;  
081:            dllNode dlnTop = dlnHead.dlnNext;  
082:            dlnTop.dlnPre.dlnNext= dlnTop.dlnNext;  
083:            dlnTop.dlnNext.dlnPre = dlnTop.dlnPre;  
084:            dlnTop.dlnPre = null;  
085:            dlnTop.dlnNext = null;  
086:            dlnTop.objNodeField = null;  
087:            dlnTop = null;  
088:            return true;  
089:       }  
090:       boolean RemoveEnd(){ //移除尾端節點  
091:            if(IsEmpty())  
092:                 return false;  
093:            dllNode dlnEnd = dlnHead.dlnPre;  
094:            dlnEnd.dlnPre.dlnNext= dlnEnd.dlnNext;  
095:            dlnEnd.dlnNext.dlnPre = dlnEnd.dlnPre;  
096:            dlnEnd.dlnPre = null;  
097:            dlnEnd.dlnNext = null;  
098:            dlnEnd.objNodeField = null;  
099:            dlnEnd = null;  
100:            return true;  
101:       }  
102:         
103:       List<Object> List(){ //列出所有節點屬性  
104:            List<Object> NodeFields = new ArrayList<Object>();  
105:            dllNode Temp = dlnHead.dlnNext;  
106:            while(Temp!=dlnHead){  
107:                 NodeFields.add(Temp.objNodeField);  
108:                 Temp = Temp.dlnNext;  
109:            }  
110:            return NodeFields;  
111:       }  
112:  }  

相關議題

• 尋找某節點的位置
• 從某節點起尋找另一個節點的位置
• 從中間插入某節點
• 從中間刪除某節點