Python データ構造のリンク リストの詳細な紹介

この記事では主に Python データ構造リンクリストの関連情報を詳しく紹介します。興味のある方は参考にしてください。

データ構造は、これまでに多くの知識がありました。教科書では C 言語を使用してリンク リストを実装します。C にはメモリを簡単に制御してリンク リストを実装できるため、他の言語ではシミュレートされたリンク リストを使用することがあまりありません。 Python は動的言語であり、オブジェクトを新しい変数に直接割り当てることができるため、リンク リストをシミュレートします。

さて、Python での実装について話す前に、リンク リストについて簡単に話させてください。大量のデータを保存する場合、配列を使用することがよくありますが、挿入操作を実行する場合は非常に面倒です。以下の例を見てください。データ 1、2、3、5、6、7 があります。 3 に挿入したい 5 と 5 の間に 4 を挿入します。配列を使用する場合はどうしますか?もちろん、5 以降のデータを 1 つ戻してから 4 を挿入するのですが、これは非常に面倒ですが、リンクリストを使用すると、3 と 5 の間に 4 を直接挿入するだけで済みますので、非常に便利そうです。

では、リンクリストの構造は何でしょうか?名前が示すように、リンク リストはもちろんチェーンのようなもので、ノードが互いに接続されてデータ チェーンを形成します。

リンクリストノードの構造は次のとおりです:

data はカスタマイズされたデータ、next は次のノードのアドレスです。

リンクリストの構造は、head が最初のノードのアドレスを保存します:

次に、Python を使用してリンクリストを実装します

Python を使用してリンクリストを実装します

まず、ノード クラス Node:

class Node:
  '''
  data: 节点保存的数据
  _next: 保存下一个节点对象
  '''
  def __init__(self, data, pnext=None):
    self.data = data
    self._next = pnext

  def __repr__(self):
    '''
    用来定义Node的字符输出，
    print为输出data
    '''
    return str(self.data)

次に、リンク リスト クラスを定義します:

リンク リストには以下が含まれます:

属性:

リスト ヘッダー: head

リンク リストの長さ: length

メソッド:

空かどうかの判定: isEmpty()

def isEmpty(self):
  return (self.length == 0

ノードの追加(リンクリストの最後に追加): append()

def append(self, dataOrNode):
  item = None
  if isinstance(dataOrNode, Node):
    item = dataOrNode
  else:
    item = Node(dataOrNode)

  if not self.head:
    self.head = item
    self.length += 1

  else:
    node = self.head
    while node._next:
      node = node._next
    node._next = item
    self.length += 1

ノードの削除: delete()

#删除一个节点之后记得要把链表长度减一
def delete(self, index):
  if self.isEmpty():
    print "this chain table is empty."
    return

  if index < 0 or index >= self.length:
    print &#39;error: out of index&#39;
    return
  #要注意删除第一个节点的情况
  #如果有空的头节点就不用这样
  #但是我不喜欢弄头节点
  if index == 0:
    self.head = self.head._next
    self.length -= 1
    return

  #prev为保存前导节点
  #node为保存当前节点
  #当j与index相等时就
  #相当于找到要删除的节点
  j = 0
  node = self.head
  prev = self.head
  while node._next and j < index:
    prev = node
    node = node._next
    j += 1

  if j == index:
    prev._next = node._next
    self.length -= 1

ノードの変更: update()

def update(self, index, data):
  if self.isEmpty() or index < 0 or index >= self.length:
    print &#39;error: out of index&#39;
    return
  j = 0
  node = self.head
  while node._next and j < index:
    node = node._next
    j += 1

  if j == index:
    node.data = data

ノードの検索: getItem()

def getItem(self, index):
  if self.isEmpty() or index < 0 or index >= self.length:
    print "error: out of index"
    return
  j = 0
  node = self.head
  while node._next and j < index:
    node = node._next
    j += 1

  return node.data

ノードのインデックスの検索: getIndex()

def getIndex(self, data):
  j = 0
  if self.isEmpty():
    print "this chain table is empty"
    return
  node = self.head
  while node:
    if node.data == data:
      return j
    node = node._next
    j += 1

  if j == self.length:
    print "%s not found" % str(data)
    return

ノードの挿入: insert( )

def insert(self, index, dataOrNode):
  if self.isEmpty():
    print "this chain tabale is empty"
    return

  if index < 0 or index >= self.length:
    print "error: out of index"
    return

  item = None
  if isinstance(dataOrNode, Node):
    item = dataOrNode
  else:
    item = Node(dataOrNode)

  if index == 0:
    item._next = self.head
    self.head = item
    self.length += 1
    return

  j = 0
  node = self.head
  prev = self.head
  while node._next and j < index:
    prev = node
    node = node._next
    j += 1

  if j == index:
    item._next = node
    prev._next = item
    self.length += 1

リンクリストをクリアする:clear()

def clear(self):
  self.head = None
  self.length = 0

上記は実装するリンクリストクラスのメソッドです。

実行結果:

以下は完全なコードです:

# -*- coding:utf8 -*-
#/usr/bin/env python

class Node(object):
 def __init__(self, data, pnext = None):
  self.data = data
  self._next = pnext

 def __repr__(self):
  return str(self.data)

class ChainTable(object):
 def __init__(self):
  self.head = None
  self.length = 0

 def isEmpty(self):
  return (self.length == 0)

 def append(self, dataOrNode):
  item = None
  if isinstance(dataOrNode, Node):
   item = dataOrNode
  else:
   item = Node(dataOrNode)

  if not self.head:
   self.head = item
   self.length += 1

  else:
   node = self.head
   while node._next:
    node = node._next
   node._next = item
   self.length += 1

 def delete(self, index):
  if self.isEmpty():
   print "this chain table is empty."
   return

  if index < 0 or index >= self.length:
   print &#39;error: out of index&#39;
   return

  if index == 0:
   self.head = self.head._next
   self.length -= 1
   return

  j = 0
  node = self.head
  prev = self.head
  while node._next and j < index:
   prev = node
   node = node._next
   j += 1

  if j == index:
   prev._next = node._next
   self.length -= 1

 def insert(self, index, dataOrNode):
  if self.isEmpty():
   print "this chain tabale is empty"
   return

  if index < 0 or index >= self.length:
   print "error: out of index"
   return

  item = None
  if isinstance(dataOrNode, Node):
   item = dataOrNode
  else:
   item = Node(dataOrNode)

  if index == 0:
   item._next = self.head
   self.head = item
   self.length += 1
   return

  j = 0
  node = self.head
  prev = self.head
  while node._next and j < index:
   prev = node
   node = node._next
   j += 1

  if j == index:
   item._next = node
   prev._next = item
   self.length += 1

 def update(self, index, data):
  if self.isEmpty() or index < 0 or index >= self.length:
   print &#39;error: out of index&#39;
   return
  j = 0
  node = self.head
  while node._next and j < index:
   node = node._next
   j += 1

  if j == index:
   node.data = data

 def getItem(self, index):
  if self.isEmpty() or index < 0 or index >= self.length:
   print "error: out of index"
   return
  j = 0
  node = self.head
  while node._next and j < index:
   node = node._next
   j += 1

  return node.data


 def getIndex(self, data):
  j = 0
  if self.isEmpty():
   print "this chain table is empty"
   return
  node = self.head
  while node:
   if node.data == data:
    return j
   node = node._next
   j += 1

  if j == self.length:
   print "%s not found" % str(data)
   return

 def clear(self):
  self.head = None
  self.length = 0

 def __repr__(self):
  if self.isEmpty():
   return "empty chain table"
  node = self.head
  nlist = &#39;&#39;
  while node:
   nlist += str(node.data) + &#39; &#39;
   node = node._next
  return nlist

 def __getitem__(self, ind):
  if self.isEmpty() or ind < 0 or ind >= self.length:
   print "error: out of index"
   return
  return self.getItem(ind)

 def __setitem__(self, ind, val):
  if self.isEmpty() or ind < 0 or ind >= self.length:
   print "error: out of index"
   return
  self.update(ind, val)

 def __len__(self):
  return self.length

以上がPython データ構造のリンク リストの詳細な紹介の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。