Python一方向チェーンテーブルの実現

チェーンテーブルは、メモリに接続する必要のない一連の構造で構成され、これらのオブジェクトは線形にソートされます.各構造には、テーブル要素と後続要素へのポインタが含まれます.最後のセルのポインタはNULLを指します.チェーンテーブルの削除と挿入操作を容易にするために、チェーンテーブルにヘッダーを追加できます.
削除操作は、ポインタを変更することによって実現できます.
挿入操作には2回のポインタ調整が必要です.
1.一方向チェーンテーブルの実現
1.1ノード実装
各ノードは2つの部分に分かれています.一部のチェーンテーブルを含む要素は、データドメインと呼ぶことができる.別の部分はポインタで、次のノードを指します.

class Node():
  __slots__=['_item','_next']  #  Node     
  def __init__(self,item):
    self._item=item
    self._next=None   #Node         None
  def getItem(self):
    return self._item
  def getNext(self):
    return self._next
  def setItem(self,newitem):
    self._item=newitem
  def setNext(self,newnext):
    self._next=newnext

1.2 SinglelinkedListの実装

class SingleLinkedList(): 
  def __init__(self):
    self._head=None  #        
    self._size=0

1.3チェーンテーブルが空であるかどうかを検出する

def isEmpty(self):
  return self._head==None

1.4 addチェーンテーブルの先端に要素を追加する

def add(self,item):
  temp=Node(item)
  temp.setNext(self._head)
  self._head=temp

1.5 appendチェーンテーブルの末尾に要素を追加

def append(self,item):
  temp=Node(item)
  if self.isEmpty():
    self._head=temp  #    ，             
  else:
    current=self._head
    while current.getNext()!=None:
      current=current.getNext()  #    
    current.setNext(temp)  #  current        

1.6 search検索要素がチェーンテーブルにあるかどうか

def search(self,item):
  current=self._head
  founditem=False
  while current!=None and not founditem:
    if current.getItem()==item:
      founditem=True
    else:
      current=current.getNext()
  return founditem

1.7 indexインデックス要素のチェーンテーブル内の位置

def index(self,item):
  current=self._head
  count=0
  found=None
  while current!=None and not found:
    count+=1
    if current.getItem()==item:
      found=True
    else:
      current=current.getNext()
  if found:
    return count
  else:
    raise ValueError('%s is not in linkedlist'%item)

1.8 removeチェーンテーブルの要素を削除する

def remove(self,item):
  current=self._head
  pre=None
  while current!=None:
    if current.getItem()==item:
      if not pre:
        self._head=current.getNext()
      else:
        pre.setNext(current.getNext())
      break
    else:
      pre=current
      current=current.getNext()

1.9 insertチェーンテーブルに要素を挿入する

def insert(self,pos,item):
  if pos<=1:
    self.add(item)
  elif pos>self.size():
    self.append(item)
  else:
    temp=Node(item)
    count=1
    pre=None
    current=self._head
    while count<pos:
      count+=1
      pre=current
      current=current.getNext()
    pre.setNext(temp)
    temp.setNext(current)

すべてのコード

class Node:
    __slots__ = ['_item', '_next']

    def __init__(self, item):
        self._item = item
        self._next = None

    def getItem(self):
        return self._item

    def getNext(self):
        return self._next

    def setItem(self, newitem):
        self._item = newitem

    def setNext(self, newnext):
        self._next = newnext


class SingleLinkedList:
    def __init__(self):
        self._head = None  #        

    def isEmpty(self):
        return self._head == None

    def size(self):
        current = self._head
        count = 0
        while current != None:
            count += 1
            current = current.getNext()
        return count

    def travel(self):
        current = self._head
        while current != None:
            print(current.getItem(),end=' ')
            current = current.getNext()
        print()

    def add(self, item):
        temp = Node(item)
        temp.setNext(self._head)
        self._head = temp

    def append(self, item):
        temp = Node(item)
        if self.isEmpty():
            self._head = temp  #     ，             
        else:
            current = self._head
            while current.getNext() != None:
                current = current.getNext()  #     
            current.setNext(temp)  #   current        

    def search(self, item):
        current = self._head
        founditem = False
        while current != None and not founditem:
            if current.getItem() == item:
                founditem = True
            else:
                current = current.getNext()
        return founditem

    def index(self, item):
        current = self._head
        count = 0
        found = None
        while current != None and not found:
            count += 1
            if current.getItem() == item:
                found = True
            else:
                current = current.getNext()
        if found:
            return count
        else:
            raise ValueError('%s is not in linkedlist' % item)

    def remove(self, item):
        current = self._head
        pre = None
        while current != None:
            if current.getItem() == item:
                if not pre:
                    self._head = current.getNext()
                else:
                    pre.setNext(current.getNext())
                break
            else:
                pre = current
                current = current.getNext()

    def insert(self, pos, item):
        if pos <= 1:
            self.add(item)
        elif pos > self.size():
            self.append(item)
        else:
            temp = Node(item)
            count = 1
            pre = None
            current = self._head
            while count < pos:
                count += 1
                pre = current
                current = current.getNext()
            pre.setNext(temp)
            temp.setNext(current)


if __name__ == '__main__':
    a = SingleLinkedList()
    for i in range(1, 10):
        a.append(i)
    print(a.size())
    a.travel()
    print(a.search(6))
    print(a.index(5))
    a.remove(4)
    a.travel()
    a.insert(4, 100)
    a.travel()

出力:
91 2 3 4 5 6 7 8 9 True51 2 3 5 6 7 8 9 1 2 3 100 5 6 7 8 9