Table of Contents¶

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

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

実装メモ¶

データの追加（add操作）¶

add操作：ここでは，最後尾にデータを追加する．

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

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

リストが空の場合：先頭ポインタを新しいセルへ更新する．

Head -> newCell

それ以外

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

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

参考

平成26年応用情報処理技術者 p.79

データの挿入（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)

参考

平成26年応用情報処理技術者 p.79

データの削除の場合（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¶

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

one_l = OnewayList()

one_l.add(1)
one_l.add(2)
one_l.add(3)
one_l.print()

1
2
3

one_l.insert(0, 4)
one_l.insert(2, 5)
one_l.insert(5, 6)

one_l.print()

4
1
5
2
3
6

one_l.del_head()

one_l.print()

1
5
2
3
6

one_l.delete(0)

one_l.print()

5
2
3
6

one_l.delete(1)

one_l.print()

5
3
6

one_l.delete(2)
one_l.print()

5
3

one_l.to_list()

[5, 3]

参考：

http://www.ced.is.utsunomiya-u.ac.jp/lecture/2011/prog/p2/kadai2/3_list_1.php

双方向リスト(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¶

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

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

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

doubly_l.deleteFirst()

doubly_l.print()
print()
doubly_l.print_reverse()

5
6
2
1
3
7

7
3
1
2
6
5

doubly_l.deleteLast()

doubly_l.print()
print()
doubly_l.print_reverse()

5
6
2
1
3

3
1
2
6
5

doubly_l.delete(0)
doubly_l.delete(2)
doubly_l.delete(1)

doubly_l.print()
print()
doubly_l.print_reverse()

6
3

3
6

doubly_l.to_list()

[6, 3]

参考

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_3_C&lang=jp

循環リスト¶

前へのポインタ，次へポインタといった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¶

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

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

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

circular_l.deleteFirst()

circular_l.print()
print()
circular_l.print_reverse()

5
6
2
1
3
7

7
3
1
2
6
5

circular_l.deleteLast()

circular_l.print()
print()
circular_l.print_reverse()

5
6
2
1
3

3
1
2
6
5

circular_l.delete(0)
circular_l.delete(2)
circular_l.delete(1)

circular_l.print()
print()
circular_l.print_reverse()

6
3

3
6

circular_l.trace(5)

6
3
6
3
6

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

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

リスト構造メモ

リスト構造メモ

Table of Contents¶

リスト構造¶

単方向リスト¶

実装メモ¶

データの追加（add操作）¶

データの挿入（insert操作）¶

データの削除の場合（delete操作）¶

単方向リストのcode¶

双方向リスト(Doubly Linked List)¶

実装メモ¶

データを末尾へ追加（addLast）¶

データを先頭へ追加（addFirst）¶

データの挿入 insert()¶

先頭データの削除 deleteFirst¶

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

データの削除 delete¶

双方向リストのcode¶

循環リスト¶

実装メモ¶

データを末尾へ追加（addLast）¶

データを先頭へ追加（addFirst）¶

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

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

循環リストのcode¶