###### tags: `LeetCode筆記`
[TOC]

# 雙向鏈結串列 💻

## 圖解概念

下圖的意思說 ptr 的左邊節點的右邊那個節點是自己，反之，ptr的又便捷點的左變節點也是自己。

## 加入節點到雙向鏈結串列

## 新增節點程式碼

小弟把更多細節的講解，都寫在了程式註解上面，因為這樣比較好可以清楚描述每一行在做什麼工作!!!

### 新增Node從尾節點
- linked list 的資料結構有 tail 和head 然後本身node 的結構還有right 和left
- 所以在接node 的時候，要把頭尾都接上去
- 最後兩行就是把尾端節點的右指標指向新節點 ，然後把新節點的左邊指標指向尾端節點

def append(self,score):
        NewNode= Node(score )
        NewNode.next=None   # in the tail, so the new node next must be None 
        
        if self.head == None : #判斷是不是空串列
            NewNode.pre=None  # 空串列時 ，則把新節點的前一個指向空的 因為上面已經把右邊鏈結指向None了
            self.head =NewNode # 把首節點當成current 的新節點
            return 
        #count to the end of list 
        last=self.head   # 建立一個temperarent node 去存loop的 節點。 
        while( last.next != None ): # 去做loop去找到最後一個node 
            last =last.next 
        #connect two side of  the new node and the oritginal end node   
        last.next =NewNode 
        NewNode.prev=last
        return

### 新增從首節點

def add(self, score ):
        NewNode= Node(score) # 丟入data 直接建立node 
        NewNode.next= self.head #因為add first, slef.head 可能為None 但沒差，都要建立連線  
        if self.head != None : 
            self.head.prev=NewNode # 首節點的左邊指向new 節點
            NewNode.next=self.head  # new node 的右邊指向原本的新節點
        else :
            self.head =NewNode  # 沒有首node ，建立新的節點 
        self.head=NewNode # change the first node name 
        print("Connected Node...")

### 新增節點從中間（指定位置）
目標位置在current 的下一個節點

# second method ...
def insert(self,data,number):
        
        newNode=Node(data )
        
        if self.head== None :
            self.add(data)
        else:
            count=1
            current=self.head 
            while number!=count:
                current=current.next
            newNode.next=current.next #新節點的下一個指向目標節點的下一個節點
            current.next.pre=newNode # 目標節點的下一個節點的上一個節點指向新節點
            newNode.pre=current # 新節點的左節點指向目標節點
            current.next=newNode # 目標節點的下一個節點指向新節點

## 刪除節點

### 刪除首節點

def delete_first(self):
        if self.head ==None:
            print("empty ")
        else:
            tem=self.head.next  #把首節點的下一個先放到暫時的節點，因為等等會斷掉連結
            self.head.next=None # 斷掉和下一個節點連結
            self.head.prev=None 
            self.head=tem #把原本的下一個節點指定為新的首節點
            del tem  #釋放 暫時節點

### 刪除最後一個節點

def delete_last(self):
        if self.head==None:
            print("list is empty ")
        else :
            tem=self.head 
            while(tem.next!= None):
        
                tem=tem.next 
            tem.prev.next=None  #把最後一個節點的上一個節點指向none(原本是指向最後的節點)
            tem.prev=None #把最後節點的左邊節點指向none  
            delete(tem)