lINKED lIST

接続リストは、データ要素の線形集合であり、データの順序は物理的な順序でメモリに格納されません。

アレイ接続リストk番目の要素のアクセスO(1)O(k)任意の場所追加/削除要素O(N)O(1)メモリ上の配置連続不連続追加所要空間(Overhead)-O(N)
接続リストはコンピュータ科学の中で配列とともに最も基本的な代表的な線形資料構造の一つであり,多様な抽象資料型(ADT)を実現する基礎である.
新しいノードを動的に挿入または削除しやすく、接続構造で物理メモリを連続的に使用する必要がないため、管理が容易です.さらに、データを構造に整理し、ポインタにリンクする概念は、様々な方法で広く応用することができる.
探索にはO(n)が必要ですが、なぜですか?->特定のインデックスにアクセスするには、インデックス全体を順番に読み込む必要があります.
始点または終点を追加、削除、またはO(1)を追加、削除または抽出できます.
ArrayとTradeOffの関係(出典:ライフコード)

接続の方向によって、3種類あります

単鎖表

デュアルリンクリスト(デュアルリンクリスト)

Circularチェーンテーブル(リング接続リスト)

リンクリストのメリットとデメリット

長所

水晶はO(1)に形成された.

を変更するたびに、動的リンクリストのサイズは、決定アレイよりも大きな空間

を最初から割り当てる必要はない.

メモリ管理が簡単

短所

ランダムアクセスで、Arrayのようにindexでナビゲートできません

ナビゲーションにはO(n)->アクセス速度が遅い

が必要

中間データ消去前後データ接続の再構成が必要な追加タスク

Implementing Linked List

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

class LinkedList:
    def __init__(self, item):
        self.head = Node(item)
        # head는 초기 시작 노드를 말한다.

    # 추가 메소드
    def add(self, item):
        cur = self.head
        # cur는 현재 찍고 있는 노드를 의미한다. (포인터 개념)

        while cur.next is not None:
            cur = cur.next
        cur.next = Node(item)

    # 삭제 메소드
    def remove(self, item):
        if self.head.val == item:
            self.head = self.head.next
        else:
            cur = self.head
            while cur.next is not None:
                if cur.val == item:
                    self.removeItem(item)
                    return
                cur = cur.next
            print("item does not exist in linked list")

    def removeItem(self, item):
        cur = self.head
        while cur.next is not None:
            if cur.next.val == item:
                nextnode = cur.next.next
                cur.next = nextnode
                break
            
    # 출력 메소드
    def printlist(self):
        cur = self.head
        print("HEAD:: ", end='')
        while cur is not None:
            print(cur.val, '->', end=' ')
            cur = cur.next
        if cur is None:
            print('empty')

    # linked list size 출력 메소드
    def size(self):
        cur = self.head
        count = 0
        while cur:
            count += 1
            cur = cur.next
        return count

    # 탐색 메소드
    def search(self, data):
        check = self.head
        for i in range(self.size()):
            if check.val == data:
                print(data, "The data is at the {} index.".format(i+1))
                return None
            check = check.next
        print(data, "Data does not exist in linked list")
        return None

linked = LinkedList(2)

linked.add(3)
linked.add(4)
linked.add(5)
linked.printlist()

linked.remove(3)
linked.printlist()

linked.search(5)
print(linked.size())
	
# HEAD:: 2 -> 3 -> 4 -> 5 -> empty
# HEAD:: 2 -> 4 -> 5 -> empty
# 5 The data is at the 3 index.
# 3