接続リスト

接続リストの定義

接続リスト(リンクリスト)は、1行のノード(データ+ポインタ(次のノードのアドレス)を含むデータ構造である.

📚 CLASS宣言

# 노드 CLASS 선언
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
# 연결 리스트 CLASS 선언
class LinkedList:
    def __init__(self):
        self.head = None
        self.count = 0

接続リストの利点

接続リストの長さを動的に調整できます
簡単にデータを挿入/削除

接続リストの欠点

任意のノードに直接アクセスできません.
次のノードの位置を格納するには、追加のスペースが必要です.
Cache Localityが近いデータをキャッシュに保存するのは難しい
接続リストをリバースブラウズできません

📚 シナリオVS接続リスト

配列された物理メモリアドレスは連続的であり、接続リストの物理メモリアドレスは連続的ではなくランダムである.
配列の挿入/削除にはO(n)の時間が必要であり,動的接続リストの挿入/削除にはO(1)の時間が必要である.
配列はO(1)の時間をインデックスとして各要素に容易にアクセスできる.ただし,接続リストにはO(n)の時間が必要である.(メモリと配列の接続方法が異なるため、データを検索するにはすべてのノードを巡回する必要があります.)

実装接続リスト

ノードの挿入

ノードの削除

    #연결리스트의 끝부분에 새로운 노드추가
    def append(self, data):
        if self.head == None:
            self.head = node
        else:
            cur = self.head
            while cur,next != None:
                cur = cur.next
            cur.next = Node(data)
            
    #모든 노드 값 출력
    def print_all(self):
        cur = self.head
        while cur != None:
            print(cur.data)
            cur = cur.next
            
    # 특정 인덱스에 있는 노드 알아내기
    def get_node(self, index):
        cnt = 0
        node = self.head
        while cnt < index:
            cnt += 1
            node = node.next
        return node
        
    #삽입
    def add_node(self, index, value):
        new_node = Node(value)
        if index == 0:
            new_node.next = self.head
            self.head = new_node
            return
        node = self.get_node(index-1)
        next_node = node.next
        node.next = new_node
        new_node.next = next_node
        
    #삭제
    def delete_node(self, index):
        if index == 0:
            self.head = self.head.next
            return
        node = self.get_node(index-1)
        node.next = node.next.next

📌 接続リストの例

📚 接続リストLEETCode 206を反転する。Reverse Linked List

from typing import Optional
from structures import ListNode

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur, prv = head, None
        while cur:
            nxt = cur.next
            cur.next = prv
            prv = cur
            cur = nxt
        return prv

cur,prvをheadとNoneにそれぞれ指向させ,繰り返し文はcurの次のノードアドレスをnxtに格納し,curの次のアドレスcurを格納する.nextをprvに保存します.では、ノードの次の順序はprvノードとその後に接続されたノードです.curノードアドレスをprvに再保存します(curの次のノードがprvに接続されているため、cur+prvをprvに保存します).Curは、元の接続リストに示されている次のノードnxtのアドレスに移動します.

🔍 1回繰り返す

cur : 1->2->3->4->5
prv : None
net : 2->3->4->5
cur.next = prv
(cur : 1->None)
prv,cur = cur,nxt
(prv : 1->None)
(cur : 2->3->4->5)

🔍 2回繰り返す

cur : 2->3->4->5
prv : 1->None
nxt : 3->4->5
cur.next = prv
(cur : 2->1->None)
prv,cur = cur,nxt
(prv : 2->1->None)
(cur : 3->4->5)
その後、繰り返し文が完了すると、input値headの接続リストが逆順序で返されます.

ポスト

半日接続リストの概念を調べてやっと分かった.最初は、入力値を設定している間に接続リスト構造としてどのように作成するかわからず、ノードがすべて出力されている間に、重複文に次のノードアドレスを入力しないと無限ループに陥り、コードの定義方法も分からず、以下のソースの文章を見て少し理解し、問題解決にも成功しました.

    head = ListNode(1)
    head.next = ListNode(2)
    head.next.next = ListNode(3)
    head.next.next.next = ListNode(4)
    head.next.next.next.next = ListNode(5)
    
    result = solution.reverseList(head)

    while result:
        print(result.val)
        result = result.next

上記の方法で値を入力すればよい.
私が普段あまり知らないhashmapやlinkedlistなどには、このような内蔵関数が隠されています.今は資料構造の入門ですが、これから学ぶことが多いと思います.接続リストの概念の開発に伴い、ますます重要になってきたと思います.
ソース:https://velog.io/@kyunghwan1207/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0Python%EC%9C%BC%EB%A1%9C-Stack-Queue-LinkedList-%EA%B5%AC%ED%98%84-bmpk4w1l
https://velog.io/@yeseolee/python-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%97%B0%EA%B2%B0%EB%A6%AC%EC%8A%A4%ED%8A%B8Linked-List-feat.LeetCode