자료구조_링크드리스트_5_리스트접근

링크드 리스트 접근 연산

- 특정 위치에 있는 노드를 리턴하는 연산

- 배열을 원하는 위치로 인덱스를 이용해서 원하는 값을 리턴할 수 있지만, 링크드리스트는 참조하고 있기 때문에 한번에 접근 할 수 없습니다. 

<출처:코드잇:자료구조>

class Node:
    """링크드 리스트의 노드 클래스"""
    def __init__(self, data):
        self.data = data # 노드가 저장하는 데이터
        self.next = None # 다음 노드에 대한 레퍼런스

class LinkedList:
    """링크드 리스트 클래스"""
    def __init__(self):
        self.head = None
        self.tail = None

    def find_node_at(self, index):
        """링크드 리스트 접근 연산 메소드, 파라미터 인덱스는 항상 있다고 가정합니다."""
        iterator = self.head;

        for _ in range(index):
            iterator = iterator.next

        return iterator

    def apppend(self, data):
        """링크드 리스트 추가 연산 메소드"""
        new_node = Node(data)

        if self.head is None: #링크드 리스트가 비어 있는 경우
            self.head = new_node
            self.tail = new_node
        else:                 #링크드 리스트가 비어 있지 않은 경우
            self.tail.next = new_node
            self.tail = new_node

    def __str__(self):
        """링크드 리스트를 문자열로 표현해서 리턴하는 메소드"""
        res_str = "|"

        # 링크드  리스트 안에 모든 노드를 돌기 위한 변수. 일단 가장 앞 노드로 정의한다.
        iterator = self.head

        # 링크드  리스트 끝까지 돈다
        while iterator is not None:
            # 각 노드의 데이터를 리턴하는 문자열에 더해준다
            res_str += f" {iterator.data} |"
            iterator = iterator.next  # 다음 노드로 넘어간다

        return res_str

find_node_at(index)를 구현하였습니다. 동작이 잘 되는 지 확인해 봅니다. 

#새로운 링크드 리스트 생성
my_list = LinkedList()
#링크드 리스트에 데이터 추가
my_list.apppend(2)
my_list.apppend(3)
my_list.apppend(5)
my_list.apppend(7)
my_list.apppend(11)

#링크드 리스트 노드에 접근(데이터 가지고 오기)
print(my_list.find_node_at(3).data)

#링크드 리스트 노드에 접근(데이터 바꾸기)
my_list.find_node_at(2).data = 13

print(my_list)

<결과>

링크드 리스트 접근 시간 복잡도

- 인덱스 x에 있는 노드에 접근 하려면 head에서 다음 노드로 x번 가면됩니다. 

- 마지막 노드에 접근하려면 head에서 다음 노드로 n-1번 가야됩니다. 

그래서 시간 복잡도는 O(n)이 됩니다. 

- 배열보다 상당히 비효율 적인 것을 알 수 있습니다.