「データ構造」接続リスト(リンクリスト)(1)

リンクリスト

ちゅうしょうデータこうぞう

データ構造の内部実装を隠す2つの(データ、Aグループ操作)を提供するデータ構造.

Data

ex.整数、文字列、レコード、...

Aオペレーションセット(一連の演算)

挿入、削除、巡回、...

ソート、ナビゲーション、...

接続リスト

...前のものが後ろにあることを示すリストです.

Node

データと1つのリンク(next)

ノードには、データだけでなく、

へのリンクも含まれています.

ノード内のデータは、異なる構造を採用することができる.

文字列、レコード、およびその他の接続リストを含む

リストの一番前を知っておくと、他のノードが見つかります.

用語

Head:

Tail:リスト末尾の

###ofノード:ノード数

リストデータと、リストに適用可能な演算とがセットになっている場合、それはリストを接続する抽象的なデータ構造である.

データ構造の定義(Node class+演算class)

1. Node class (Data+Link)

class Node:
	def __init__(self, item):
    	self.data = item
        self.next = None

class LinkedList"
	def __init__(self):
    	# 비어 있는 연결 리스트
    	self.nodeCount = 0
        self.head = None
        self.tail = None

2.演算クラス

演算定義

特定の要素(k)

を参照してください.

リスト巡回

の長さ

を得る

要素

を挿入

要素

を削除

の2つのリストが

にマージされます.

特定の要素を参照してください.
posにある2番目のノードを見つけ、ノード

に戻る

def getAt(self, pos):
	if pos <= 0 or pos > self.nodeCount:
    	return None
    i = 1
    curr = self.head
    while i < pos:
    	curr = curr.next
        i += 1
    return curr

アレイvs接続リスト

配列接続リスト記憶空間連続位置指定特定要素は非常に単純である(O(1)O(1)O(1)O(1)O(1)O(n)O(n)O(n)O(n)O(n)O(n)