はしくれエンジニアもどきのメモ

情報系技術・哲学・デザインなどの勉強メモ・備忘録です。

リスト構造メモ

リスト構造メモ

リスト構造

 

単方向リスト

 

ポインタには次のセルの場所が位置付けられていて, 一方向にだけたどるリスト構造.

特徴: データの挿入,追加,削除がポインタ変更によって容易.

最後のセルはデータのみ持ち,ポインタはどこも指さない.

データアドレス    次のポインタ
30 (先頭セル)       50
                    ↓
50                  70
                    ↓
70                  110
                    ↓
110                 90
                    ↓
90                  NULL

Fig.単方向リストのイメージ図

 

実装メモ

 

データの追加(add操作)

 

add操作: ここでは,最後尾にデータを追加する.

線形リストの最後のセルを求めて,最後のセルの次のポインタに新しいセルを追加する.

データが増えるたびに,最後尾まで求める必要があるので, 処理量が増えていく.

  • リストが空の場合:先頭ポインタを新しいセルへ更新する.
Head -> newCell
  • それ以外

最後尾のセルを求めて,最後尾のセルの次のポインタを新しいセルにする.

Head -> Cell(1) -> Cell(2) -- -> Cell(n) -> newCell

参考

 

データの挿入(insert操作)

 

insert操作:

任意のindexを指定して,そこに新しいセルを挿入する.

  • 先頭へ挿入する場合

「新しいセルの次ポインタ」に元々の先頭ポインタのセルを追加し, 「先頭ポインタ」を新しいセルへ更新する.

old Head -> Cell(1) -> Cell(2) -- -> Cell(n)
new Head -> newCell -> Cell(1) -> Cell(2) -- -> Cell(n)
  • indexへ挿入する場合: i-1番目のセルとi番目のセルを求めて,
    • 「i-1番目のセルの次ポインタ」に新しいセルを指定.
    • 「新しいセルの次ポインタ」にi番目のセルを指定
old Head -> Cell(1) --> Cell(i-1) ->  Cell(i) -- -> Cell(n)
new Head -> Cell(1) --> Cell(i-1) ->  newCell -> Cell(i) -- -> Cell(n)

参考

 

データの削除の場合(delete操作)

 
  • 先頭を削除:Headを「先頭セルの次ポインタ」にする.先頭セルを削除する.
old Head -> Cell(1) -> Cell(2) -> -- -> Cell(n)
new Head -> Cell(2) -> -- -> Cell(n)
del Cell(1)
  • i番目を削除: 「i-1番目のセルの次ポインタ」をi+1番目のセルにする. i番目のセルを削除する.
old Head -> Cell(1) -> Cell(2) -> --> Cell(i-1) -> Cell(i) -> Cell(i+1) -- -> Cell(n)
new Head -> Cell(1) -> Cell(2) -> --> Cell(i-1) -> Cell(i+1) -- -> Cell(n)
del Cell(i)
 

単方向リストのcode

In [7]:
class Cell:
    """
    cell of one-way list
    """ 
    def __init__(self, data): # コンストラクタ
        self.data = data
        self.next_pointer = None
        
class OnewayList:
    '''
    '''
    def __init__(self):  # コンストラクタ
        self.head = None
        
    def last(self):
        cell = self.head
        # 空の時
        if not cell:
            return None
        
        # 空でないとき
        while not cell.next_pointer == None:
            # 次のポインタが空になるまで
            cell = cell.next_pointer
        return cell
    
    def get_index_cell(self, index):
        '''
        if index=0, return head 
        '''
        cell = self.head
        for i in range(index):
            cell = cell.next_pointer
        return cell
    
    def add(self, data):
        added_cell = Cell(data)
        last_cell = self.last()
        
        if not last_cell:
            self.head = added_cell
        else:
            last_cell.next_pointer = added_cell
    
    def insert(self, index, data):
        '''
        '''
        added_cell = Cell(data)
        
        # 先頭へ追加する場合
        if index == 0:
            added_cell.next_pointer = self.head
            self.head = added_cell
            return 
        
        # indexへ追加する場合
        if index > 0:
            pre_cell = self.get_index_cell(index-1)
            next_cell = pre_cell.next_pointer
            
            pre_cell.next_pointer = added_cell
            added_cell.next_pointer = next_cell
    
    def del_head(self):
        head_cell = self.head
        self.head = head_cell.next_pointer
        del head_cell
    
    def delete(self, index):
        '''
        削除対象がnullでない前提
        '''
        if index == 0:
            self.del_head()
            return 
        
        if index > 0:
            pre_cell = self.get_index_cell(index-1)
            del_target_cell = pre_cell.next_pointer
            next_cell = del_target_cell.next_pointer
            pre_cell.next_pointer = next_cell
            
            del del_target_cell
    
    def to_list(self):
        cell = self.head
        arr = []
        # 空でないとき
        while not cell == None:
            arr.append(cell.data)
            # 次のポインタが空になるまで
            cell = cell.next_pointer
        return arr
        
    def print(self):
        cell = self.head
        # 空でないとき
        while not cell == None:
            print(cell.data)
            cell = cell.next_pointer
In [12]:
one_l = OnewayList()

one_l.add(1)
one_l.add(2)
one_l.add(3)
one_l.print()
 
1
2
3
In [13]:
one_l.insert(0, 4)
one_l.insert(2, 5)
one_l.insert(5, 6)

one_l.print()
 
4
1
5
2
3
6
In [14]:
one_l.del_head()

one_l.print()
 
1
5
2
3
6
In [15]:
one_l.delete(0)

one_l.print()
 
5
2
3
6
In [16]:
one_l.delete(1)

one_l.print()
 
5
3
6
In [17]:
one_l.delete(2)
one_l.print()
 
5
3
In [18]:
one_l.to_list()
Out[18]:
[5, 3]
 

双方向リスト(Doubly Linked List)

 

平成22年基本情報技術者 p.133

前のセルへのポインタと次のセルへのポインタといった2つのポインタを持たせ,前後に自由にリストを辿れる.

最後のセルは前のポインタのみ持っている.

データアドレス        ポインタ
30 (先頭セル)     pre:Null next:50
                    ↑       ↓
50                 pre:30  next:70
                    ↑       ↓
70                 pre:50  next:110
                    ↑        ↓
110                pre:70  next:90
                    ↓        ↓
90                 pre:110 next:NULL

Fig. 双方向リストのイメージ図

 

実装メモ

 

データを末尾へ追加(addLast)

 

addLast

  • 空の場合: HeadとTailは,新しいセルを指すようにする.
Head -> newCell <- Tail
  • 空でない場合: (1)「元のTailのセルの次ポインタ」を新しいセルにする. (2) Tailを新しいセルへ更新する.
old: Head -> Cell1 <- Tail
new: Head -> Cell1 -> (1)newCell <- (2)Tail
 

データを先頭へ追加(addFirst)

 

addFirst:先頭へ追加

  • 空の場合:addLastと同じ.
Head -> newCell <- Tail
  • 空でない場合:

(1)「元のHeadのセルの前ポインタ」を新しいセルにする. (2) Headを新しいセルへ更新する.

old: Head -> Cell1 <- Tail

                            -> 
new: Head(2) -> newCell        Cell1 -> Tail
                        (1) <-
 

データの挿入 insert()

 

index目に挿入

  • 先頭に挿入:addFirst

  • 末尾に挿入:addLast

  • index目に挿入:

(1): index-1番目のセルと新しいセルを連結. (2): 新しいセルとindex番目のセルを連結.

                   -->           ->         
old: Head -> Cell1     Cell(i-1)   Cell(i) <- Tail
                   <--           <-

                  -->            ->         ->
old: Head -> Cell1     Cell(i-1) (1) newCell (2) Cell(i) <- Tail
                   <--           <-         <-
 

先頭データの削除 deleteFirst

 

deleteFirst:先頭データの削除

(1)先頭セルから「2番目のセルの前ポインタ」をNULLへ (2)Headは2番目のセルを指すようにする. (3)先頭セルの削除

                   ->                
old: Head -> Cell1     Cell2 <- Tail
                   <-       

new: Head (2) -> Cell2 <- Tail
      (1)NULL <-   
(3) del Cell1
 

末尾データの削除(deleteLast)

 

(1)末尾セルから「2番目のセルの次ポインタ」をNULLへ (2)Tailは2番目のセルを指すようにする. (3)末尾セルの削除

                   -->           ->       
old: Head -> Cell1     Cell(n-1)    Cell(n) <- Tail
                   <--           <-
                  -->                
new: Head -> Cell1    Cell(n-1) <- (2) Tail
                  <--           -> (1)NULL   
(3) del Cell(n)
 

データの削除 delete

 

データの削除 delete:任意のindexのデータを削除

  • 先頭の場合:deleteFirst
  • 末尾の場合:deleteLast
  • それ以外:

(1)「i-1番目のセル」と「i+1番目のセル」を連結. (2) i番目のセルを削除する.

                    -->           ->         ->
old Head -> Cell(1)     Cell(i-1)    Cell(i)    Cell(i+1) -- -> Cell(n) <- Tail
                    <--           <-         <-

                   -->           ->
new Head -> Cell(1)    Cell(i-1) (1) Cell(i+1) -- -> Cell(n)
                   <--           <-
(2)del Cell(i)
 

双方向リストのcode

In [19]:
class DoubleCell:
    """
    cell of doubly-lnked list
    """ 
    def __init__(self, data): # コンストラクタ
        self.data = data
        self.pre_pointer = None
        self.next_pointer = None
        
class DoublyLinkedList:
    '''
    '''
    def __init__(self): # コンストラクタ
        self.head = None
        self.tail = None
    
    def get_index_cell(self, index):
        '''
        index=0:return head 
        '''
        cell = self.head
        for i in range(index):
            cell = cell.next_pointer
        return cell
    
    def _update_doubly_linked_2cells(self, pre_cell, next_cell):
        pre_cell.next_pointer = next_cell
        next_cell.pre_pointer = pre_cell
    
    def _add_init(self, cell):
        self.tail = cell # update list.tail
        self.head = cell # update list.head
    
    def addLast(self, data):
        added_cell = DoubleCell(data)

        # 空の場合
        if (not self.head) and (not self.tail):
            self._add_init(added_cell)
            return
        
        # not empty
        self._update_doubly_linked_2cells(self.tail, added_cell)
        self.tail = added_cell # update list.tail     
    
    def addFirst(self, data):
        added_cell = DoubleCell(data)
        
        # 空の場合
        if (not self.head) and (not self.tail):
            self._add_init(added_cell)
            return
        
        # not empty
        self._update_doubly_linked_2cells(added_cell, self.head)
        self.head = added_cell # update list.head            
   
    def insert(self, index, data):
        '''
        
        '''
        added_cell = DoubleCell(data)
        
        # 先頭へ追加する場合
        if index == 0:
            self.addFirst(data)
            return 
        
        # index目に挿入        
        if index > 0:
            pre_cell = self.get_index_cell(index-1)
            
            # 最後に追加する場合
            if pre_cell == self.tail:
                self.addLast(data)
                return
            
            # index目に挿入 
            next_cell = pre_cell.next_pointer
            self._update_doubly_linked_2cells(pre_cell, added_cell)
            self._update_doubly_linked_2cells(added_cell, next_cell)
            
    
    def deleteFirst(self):
        head_cell = self.head
        second_cell = head_cell.next_pointer
        
        if not second_cell == None:
            second_cell.pre_pointer = None
        
        self.head = second_cell
        del head_cell
        
    
    def deleteLast(self):
        last_cell = self.tail
        second_cell = last_cell.pre_pointer
        
        if not second_cell == None:
            second_cell.next_pointer = None
        
        self.tail = second_cell
        del last_cell
    
    def delete(self, index):
        '''
        削除対象がnullでない前提
        '''
        # 先頭の削除
        if index == 0:
            self.deleteFirst()
            return
        
        # delete cell[index]
        if index > 0:
            pre_cell = self.get_index_cell(index-1)
            del_target_cell = pre_cell.next_pointer
            
            # 末尾の削除
            if del_target_cell == self.tail:
                self.deleteLast()
                return 
            
            # delete cell[index]
            next_cell = del_target_cell.next_pointer
            self._update_doubly_linked_2cells(pre_cell, next_cell)
            del del_target_cell
    
    def to_list(self):
        cell = self.head
        arr = []
        # 空でないとき
        while not cell == None:
            arr.append(cell.data)
            # 次のポインタが空になるまで
            cell = cell.next_pointer
        return arr
        
    
    def print(self):
        cell = self.head
        # 空でないとき
        while not cell == None:
            print(cell.data)
            cell = cell.next_pointer

    def print_reverse(self):
        cell = self.tail
        # 空でないとき
        while not cell == None:
            print(cell.data)
            cell = cell.pre_pointer
In [20]:
doubly_l = DoublyLinkedList()
doubly_l.addLast(1)
doubly_l.addFirst(2)
doubly_l.addLast(3)

doubly_l.print()
print()
doubly_l.print_reverse()
 
2
1
3

3
1
2
In [21]:
doubly_l.insert(0, 4)
doubly_l.insert(1, 5)
doubly_l.insert(2, 6)
doubly_l.insert(6, 7)

doubly_l.print()
print()
doubly_l.print_reverse()
 
4
5
6
2
1
3
7

7
3
1
2
6
5
4
In [22]:
doubly_l.deleteFirst()

doubly_l.print()
print()
doubly_l.print_reverse()
 
5
6
2
1
3
7

7
3
1
2
6
5
In [23]:
doubly_l.deleteLast()

doubly_l.print()
print()
doubly_l.print_reverse()
 
5
6
2
1
3

3
1
2
6
5
In [24]:
doubly_l.delete(0)
doubly_l.delete(2)
doubly_l.delete(1)

doubly_l.print()
print()
doubly_l.print_reverse()
 
6
3

3
6
In [25]:
doubly_l.to_list()
Out[25]:
[6, 3]
 

循環リスト

 

前へのポインタ,次へポインタといった2つのポインタを持ったリスト

双方向リストとの違いは,最後のセルの次ポインタに戦闘データのセルのアドレスを持つ. 感情に連結したリストになる.

データアドレス        ポインタ
30 (先頭ポインタ) pre:Null next:50
                    ↑       ↓
50                 pre:30  next:70
                    ↑       ↓
70                 pre:50  next:110
                    ↑        ↓
110                pre:70  next:90
                    ↓        ↓
90                 pre:110 next:30
 

実装メモ

 

基本は,双方向リストと同じ.

HeadとTailの更新があったとき,Tailのセルの次ポインタをHeadのセルに変更する.

 

データを末尾へ追加(addLast)

 

データを末尾へ追加(addLast):

新しいデータが末尾へ来るので,次ポインタを先頭セルへ更新する.

old: Head -> Cell1 <- Tail

new:               ->       ->
     Head -> Cell1    Cell2    newCell <- Tail
               |   ->       ->    |
               |-------------------
 

データを先頭へ追加(addFirst)

 

新しいデータが先頭になるので,末尾セルの次ポインタを先頭セルへ更新する.

old: Head -> Cell1 <- Tail

new:                  ->      -> 
     Head -> newCell     Cell1   Cell2 <- Tail
               |      <-      <-   |
               |--------------------
 

データの先頭を削除 deleteFirst()

 

先頭セルが2番目のセルに変わるので,末尾セルの次ポインタを2番目のセルへ変更する.

                   ->        ->        
old: Head -> Cell1     Cell2    Cell3 <- Tail
               |    <-       <-   |
               --------------------

                   ->
new: Head -> Cell2   Cell3 <- Tail
               |   <-  |
               <--------
del Cell1
 

データの末尾を削除(deleteLast())

 

末尾セルが(後ろから)2番目のセルに変わるので,2番目のセルの次ポインタを先頭セルへ変更する.

                   -->           ->        
old: Head -> Cell1     Cell(n-1)    Cell(n) <- Tail
               |   <--           <-    |
               -------------------------

                   -->
new: Head -> Cell1     Cell(n-1) <- Tail
               |   <--    |
               <----------
del Cell(n)
 

循環リストのcode

In [28]:
class DoubleCell:
    """
    cell of doubly-lnked list
    """ 
    def __init__(self, data): # コンストラクタ
        self.data = data
        self.pre_pointer = None
        self.next_pointer = None
        
class CircularList:
    '''
    '''
    def __init__(self): # コンストラクタ
        self.head = None
        self.tail = None
    
    def get_index_cell(self, index):
        '''
        if index=0, return head 
        '''
        cell = self.head
        for i in range(index):
            cell = cell.next_pointer
        return cell
    
    def _update_doubly_linked_2cells(self, pre_cell, next_cell):
        pre_cell.next_pointer = next_cell
        next_cell.pre_pointer = pre_cell
    
    def _add_init(self, cell):
        self.tail = cell # update list.tail
        self.head = cell # update list.head
        cell.next_pointer = self.head # update chain
    
    def addLast(self, data):
        added_cell = DoubleCell(data)

        # 空の場合
        if (not self.head) and (not self.tail):
            self._add_init(added_cell)
            return
        
        # not empty
        self._update_doubly_linked_2cells(self.tail, added_cell)
        self.tail = added_cell # update list.tail
        self.tail.next_pointer = self.head # update chain
            
    def addFirst(self, data):
        added_cell = DoubleCell(data)
        
        # 空の場合
        if (not self.head) and (not self.tail):
            self._add_init(added_cell)
            return
        
        # not empty
        self._update_doubly_linked_2cells(added_cell, self.head)
        self.head = added_cell # update list.head  
        self.tail.next_pointer = self.head # update chain
   
    def insert(self, index, data):
        '''
        
        '''
        added_cell = DoubleCell(data)
        
        # 先頭へ追加する場合
        if index == 0:
            self.addFirst(data)
            return 
        
        # index目に挿入        
        if index > 0:
            pre_cell = self.get_index_cell(index-1)
            
            # 最後に追加する場合
            if pre_cell == self.tail:
                self.addLast(data)
                return
            
            # index目に挿入 
            next_cell = pre_cell.next_pointer
            self._update_doubly_linked_2cells(pre_cell, added_cell)
            self._update_doubly_linked_2cells(added_cell, next_cell)
            
    
    def deleteFirst(self):
        head_cell = self.head
        second_cell = head_cell.next_pointer
        
        self.head = second_cell    
        if not second_cell == None:
            second_cell.pre_pointer = None
            self.tail.next_pointer = self.head # update chain
        
        del head_cell
    
    def deleteLast(self):
        last_cell = self.tail
        second_cell = last_cell.pre_pointer
        
        self.tail = second_cell
        if not self.tail == None:
            self.tail.next_pointer = self.head # update chain
        
        del last_cell
    
    def delete(self, index):
        '''
        削除対象がnullでない前提
        '''
        # 先頭の削除
        if index == 0:
            self.deleteFirst()
            return
        
        # delete cell[index]
        if index > 0:
            pre_cell = self.get_index_cell(index-1)
            del_target_cell = pre_cell.next_pointer
            
            # 末尾の削除
            if del_target_cell == self.tail:
                self.deleteLast()
                return 
            
            # delete cell[index]
            next_cell = del_target_cell.next_pointer
            self._update_doubly_linked_2cells(pre_cell, next_cell)
            del del_target_cell
    
    def to_list(self):
        cell = self.head
        last_cell = self.tail
        arr = []
        # 空でないとき
        while not cell == last_cell:
            arr.append(cell.data)
            # 次のポインタが空になるまで
            cell = cell.next_pointer
        arr.append(cell.data)
        return arr
        
    def print(self):
        cell = self.head
        last_cell = self.tail
        # 空でないとき
        while not cell == last_cell:
            print(cell.data)
            cell = cell.next_pointer
        print(cell.data)
    
    def print_reverse(self):
        cell = self.tail
        first_cell = self.head
        # 空でないとき
        while not cell == first_cell:
            print(cell.data)
            cell = cell.pre_pointer
        print(cell.data)
    
    def trace(self, n):
        cell = self.head
        for i in range(n):
            print(cell.data)
            cell = cell.next_pointer
In [29]:
circular_l = CircularList()
circular_l.addLast(1)
circular_l.addFirst(2)
circular_l.addLast(3)

circular_l.print()
print()
circular_l.print_reverse()
 
2
1
3

3
1
2
In [30]:
circular_l.insert(0, 4)
circular_l.insert(1, 5)
circular_l.insert(2, 6)
circular_l.insert(6, 7)

circular_l.print()
print()
circular_l.print_reverse()
 
4
5
6
2
1
3
7

7
3
1
2
6
5
4
In [31]:
circular_l.deleteFirst()

circular_l.print()
print()
circular_l.print_reverse()
 
5
6
2
1
3
7

7
3
1
2
6
5
In [32]:
circular_l.deleteLast()

circular_l.print()
print()
circular_l.print_reverse()
 
5
6
2
1
3

3
1
2
6
5
In [33]:
circular_l.delete(0)
circular_l.delete(2)
circular_l.delete(1)

circular_l.print()
print()
circular_l.print_reverse()
 
6
3

3
6
In [34]:
circular_l.trace(5)
 
6
3
6
3
6