[Python 자료구조] 링크드 리스트 (Linked List)

링크드 리스트란?

CodeIt 자료구조 수업을 정리한 내용입니다.

링크드 리스트

• 배열이나 동적 배열처럼 데이터를 순서대로 저장
• 동적 배열처럼 요소를 계속 추가 가능

노드

노드 객체는 2가지의 속성을 가지고 있습니다. data와 next로 이루어져 있는데

data는 저장하고자 하는 정보를 말하며, next는 다음 노드의 레퍼런스를 말합니다.

첫번째 노드 객체는 head 노드라고 하며 head 노드의 메모리주소만 알고 있으면

연결되어 있는 모든 노드를 접근할 수 있습니다. (실제 메모리에선 여기저기 흝어져있음)

class Node:
    def __init__(self, data):
        # 인스턴스 변수들의 초기값 setting
        self.data = data  # 노드 저장 데이터
        self.next = None  # 다음 노드에 대한 레퍼런스


# 데이터 2,5,6,9,10 담는 노드 생성
head_node = Node(2)
node_1 = Node(5)
node_2 = Node(6)
node_3 = Node(9)
tail_node = Node(10)

# 노드 연결
head_node.next = node_1
node_1.next = node_2
node_2.next = node_3
node_3.next = tail_node

# 노드 출력
iterator = head_node
while iterator is not None:
    print(iterator.data)
    iterator = iterator.next


class LinekdList:
    def __init__(self):
        self.head = None
        self.tail = None

    def __str__(self):
        res_str = "|"

        # 모든 노드를 확인하기 위해선 가장 head를 가지고 시작
        iterator = self.head
        while iterator is not None:
            res_str += f" {iterator.data} |"
            iterator = iterator.next

        return res_str

    def append(self, data):
        """
        링크드 리스트 추가 메소드
        :param data:
        :return:
        """
        # 새로운 링크드 리스트 노드 생성
        new_node = Node(data)
        if self.head is None:  # 링크드 리스트가 비어있는 경우
            self.head = new_node  # 1개이면 head이자 tail
            self.tail = new_node
        else:  # 링크드 리스트가 비어있지 않은 경우
            self.tail.next = new_node  # 기존 tail의 next를 생성한 노드랑 연결
            self.tail = new_node  # tail 생성한 노드로 변경


first_list = LinekdList()

first_list.append(2)
first_list.append(5)
first_list.append(19)
first_list.append(10)
first_list.append(23)

print(first_list)

링크드 리스트 접근연산

• 특정 위치에 있는 노드를 리턴하는 연산
  • 헤더부터 시작해서 순차적으로 확인
    • 인덱스 x 노드에 접근시 head에서 x번 이동

시간 복잡도

배열에서 접근하는 것과 달리 효율적이지 못합니다.

인덱스 x에 노드에 접근할 때 x가 마지막 인덱스일시 전체를 확인해야하는 비효율이 발생합니다.

결론적으로 접근 연산 시간 복잡도는 O(n) 입니다.

class Node:
    def __init__(self, data):
        # 인스턴스 변수들의 초기값 setting
        self.data = data  # 노드 저장 데이터
        self.next = None  # 다음 노드에 대한 레퍼런스


# 데이터 2,5,6,9,10 담는 노드 생성
head_node = Node(2)
node_1 = Node(5)
node_2 = Node(6)
node_3 = Node(9)
tail_node = Node(10)

# 노드 연결
head_node.next = node_1
node_1.next = node_2
node_2.next = node_3
node_3.next = tail_node

class LinekdList:
    def __init__(self):
        self.head = None
        self.tail = None

    def __str__(self):
        res_str = "|"

        # 모든 노드를 확인하기 위해선 가장 head를 가지고 시작
        iterator = self.head
        while iterator is not None:
            res_str += f" {iterator.data} |"
            iterator = iterator.next

        return res_str

    # 접근연산
    def find_node_at(self, index):
        iterator = self.head  # head에서 시작
        for _ in range(index):  # 인덱스 x 노드에 접근시 head에서 x번 이동
            iterator = iterator.next  # for를 다 돌면 찾고자 하는 index

        return iterator

    def append(self, data):
        # 링크드 리스트 추가 메소드
        # 새로운 링크드 리스트 노드 생성
        new_node = Node(data)
        if self.head is None:  # 링크드 리스트가 비어있는 경우
            self.head = new_node  # 1개이면 head이자 tail
            self.tail = new_node
        else:  # 링크드 리스트가 비어있지 않은 경우
            self.tail.next = new_node  # 기존 tail의 next를 생성한 노드랑 연결
            self.tail = new_node  # tail 생성한 노드로 변경


first_list = LinekdList()

first_list.append(2)
first_list.append(5)
first_list.append(19)
first_list.append(10)
first_list.append(23)

print(first_list)

print(first_list.find_node_at(3).data)  # | 2 | 5 | 19 | 10 | 23 |
first_list.find_node_at(3).data = 13
print(first_list)  # | 2 | 5 | 19 | 13 | 23 |

링크드 리스트 삽입연산

    def insert_after(self, target_node, data):
        # 링크드 리스트 주어진 노드 뒤 삽입 연산 (append와 차이는 기준을 정할 수 있음)
        new_node = Node(data)

        # tail node 다음에 삽입 (가장 끝에 추가)
        if self.tail is target_node:  # 꼬리가 타겟일때
            self.tail.next = new_node  # 해당 꼬리의 다음은 new node
        # 두 노드 사이에 삽입시
        else:
            # 삽입할 노드의 다음부터 설정
            new_node.next = target_node.next
            # 타겟 노드의 다음을 삽입할 노드로 설정
            target_node.next = new_node

    def prepend(self, data):
        # 링크드 리스트의 가장 앞 데이터 삽입
        new_node = Node(data)
        if self.head is None: # 길이가 0일때 추가시 tail, head 설정
            self.head = new_node
            self.tail = new_node
        else: # 값이 있을때 삽입할 노드의 다음을 head 설정 이후 삽입데이터를 head로
            new_node.next = self.head
            self.head = new_node

링크드 리스트 삭제연산

 # 링크드 리스트 삭제 연산, 주어진 노드 다음 노드를 삭제
    def delete_after(self, prev_node):
        data = prev_node.next.data  # 지워지는 데이터의 노드를 리턴

        # 삭제 대상이 꼬리일때
        if prev_node.next is self.tail:  # is는 레퍼런스 비교
            self.tail = prev_node  # prev값을 꼬리를 새로 지정
            prev_node.next = None  # next None setting
        else:
            # 해당 prev_node의 다음을 건너건너의 값으로 변경
            prev_node.next = prev_node.next.next

        return data

    # head 노드를 삭제할 수 없는 delete_after의 단점 보완
    def pop_left(self):
        # 지우려는 노드가 하나이거나 그렇지 않을떄
        data = self.head.data
        if self.head is self.tail:
            self.head = None
            self.tail = None
        else:
            self.head = self.head.next  # 다음 노드를 head로 지정
        return data

연산 시간복잡도

접근

인덱스 x에 있는 데이터에 접근하려면 head 노드부터 순차적으로 x번 다음 노드를 확인해야합니다.

접근은 노드의 갯수와 비례한다는 것을 알 수 있으며 최악의 경우 head노드부터 n-1번까지 이동해야합니다.

소요 시간은 최악의 경우 O(n) 시간복잡도를 가집니다.

탐색

배열을 탐색할 때와 같은 방법으로 진행합니다. 가장 앞 노드부터 순차적으로 보며 원하는 데이터를 찾습니다.

이런 방법은 선형탐색으로 최악의 경우 n개의 노드를 모두 확인해야합니다.

마찬가지로 최악의 경우 O(n) 시간복잡도를 가집니다.

삽입/삭제

insert_after, delete_after같은 함수들은 해당 위치에 삽입 또는 주변 노드에 연결된 레퍼런스만 수정합니다. 해당 연산들은 늘 일정하며 파라미터로 받는 기준 노드가 어떤 것이든 상관없이

걸리는 시간은 동일하게 O(1)의 시간복잡도를 가집니다.

연산	시간복잡도
접근	O(n)
탐색	O(n)
삽입	O(1)
삭제	O(1)

현실적 시간복잡도

연산	시간복잡도
접근	O(n)
탐색	O(n)
원하는 노드에 접근 or 탐색 + 삽입	O(n+1)
원하는 노드에 접근 or 탐색 + 삭제	O(n+1)

삽입과 삭제 연산은 특정 노드를 기준으로 다음 순서에 삽입 또는 삭제했습니다.

이 연산을 넘겨주는 node를 먼저 찾는 연산이 발생하는데 이때 head와 tail은 바로 찾을 수 있지만

그외 노드들은 탐색이나 접근 연산(find_node_at) -> O(n)을 통해 가져와야 합니다.

사실 탐색으로 인해 n을 공유하게 되는 상황이 발생하게 됩니다.

대신 append, prepend, pop_left함수들은 head, tail등으로 한번에 접근하여

데이터를 변경하기에 시간복잡도는 다음과 같습니다.

연산	시간복잡도
head에 접근 + 삽입	O(1+1)
head에 접근 + 삭제	O(1+1)
tail에 접근 + 삽입	O(1+1)
tail prev에 접근 + 삭제	O(n+1)

4번째 마지막 꼬리의 prev 접근하여 삭제의 경우 head노드에서 출발하여 n-2번 노드로 접근하여서 제거해야합니다.

이 때문에 O(n)의 시간복잡도를 가지게 되고 추가로 한번의 삭제가 일어나기에 O(n+1)로 구성됩니다.

더블리 링크드 리스트

어떤 노드던지 앞, 뒤 노드에 모두 접근할 수 있는 특징이 있습니다.

이는 전 노드와 다음 노드에 대해 쉽게 접근할 수 있는 의미입니다.

한 노드를 통해 앞에 있는 노드와 동시에 뒤에 노드를 접근하고 싶다면

싱글 링크드 리스트가 아니라 더블리 링크드 리스트를 사용하는 것이 좋습니다.

추가적 공간은 싱글리 링크드 리스트와 같은 O(n)의 크기를 가집니다.

더블리 링크드 리스트 접근 & 탐색

접근과 탐색은 싱글리 링크드 리스트와 동일합니다.

순차적으로 데이터를 확인하며 노드를 찾기 때문에 시간복잡도는 O(n) 이 걸립니다.

더블리 링크드 리스트 삽입 & 삭제

삽입연산은 특정 노드의 다음 위치에 새 노드를 추가해줍니다. 연산은 O(1)이 걸립니다.

삭제 연산은 제거하고자 하는 노드를 받아 그 노드를 그대로 지웠습니다.

이때 길이가 1개인경우, 지우고자 하는 노드가 head인 경우, 지우고자 하는 노드가 tail인 경우,

마지막으로 tail, head가 아닌 사이에 노드를 지우는 경우 4가지가 있었습니다.

이때도 마찬가지로 연산은 O(1)이 걸리게 됩니다.

더블리 링크드 리스트 현실적 시간복잡도

연산	시간복잡도
접근	O(n)
탐색	O(n)
원하는 노드에 접근 or 탐색 + 삽입	O(n+1)
원하는 노드에 접근 or 탐색 + 삭제	O(n+1)

삽입과 삭제 연산은 특정 노드를 기준으로 다음 순서에 삽입 또는 삭제했습니다.

싱글리 vs 더블리 링크드 리스트 tail 노드 삭제

연산	싱글리 링크드 리스트	더블리 링크드 리스트
가장 앞에 접근 + 삽입	O(1+1)	O(1+1)
가장 앞에 접근 + 삭제	O(1+1)	O(1+1)
가장 뒤에 접근 + 삽입	O(1+1)	O(1+1)
가장 뒤에 접근 + 삭제	O(n + 1)	O(1+1)

싱글리 링크드 리스트의 삭제 연산은 위 설명에 있듯이 바로 전 위치의 노드를 파라미터로 받습니다.

원하는 tail 노드를 지우기 위해선 지우고자 하는 노드의 prev 노드를 보내줌으로써접근 시간이 O(n)번이 걸립니다.

더블리 링크드 리스트의 경우 삭제시 지우고자 하는 노드 자체를 파라미터로 받습니다.

더블리 링크드 노드는 prev와 next에 접근할 수 있기에 효율적으로 바로 삭제할 수 있어 O(1)이 걸립니다.

더블리 링크드 리스트 코드 구현

# double은 이전, 다음의 값을 알 수 있다.
class Node:
    def __init__(self, data):
        # 인스턴스 변수들의 초기값 setting
        self.data = data  # 노드 저장 데이터
        self.prev = None  # 이전 노드에 대한 레퍼런스
        self.next = None  # 다음 노드에 대한 레퍼런스

class LinekdList:
    def __init__(self):
        self.head = None
        self.tail = None

    def __str__(self):
        res_str = "|"

        # 모든 노드를 확인하기 위해선 가장 head를 가지고 시작
        iterator = self.head
        while iterator is not None:
            res_str += f" {iterator.data} |"
            iterator = iterator.next

        return res_str

    # 접근연산
    def find_node_at(self, index):
        iterator = self.head  # head에서 시작하여 순차적으로 n번 접근
        for _ in range(index):  # 인덱스 x 노드에 접근시 head에서 x번 이동
            iterator = iterator.next  # for를 다 돌면 찾고자 하는 index

        return iterator

    # 탐색, 해당 데이터가 있는 노드 추출
    def find_node_with_data(self, data):
        iterator = self.head  # head에서 시작하여 순차적으로 n번 접근
        result = None  # 없으면 None return
        while iterator is not None:
            if iterator.data == data:
                result = iterator
                break
            iterator = iterator.next
        return result

    # 링크드 리스트 추가 연산
    def append(self, data):
        new_node = Node(data)
        # 리스트의 값이 하나도 없을때
        if self.head is None:
            self.head = new_node
        else:
            new_node.prev = self.tail
            self.tail.next = new_node
        self.tail = new_node

    def insert_after(self, prev_node, data):
        new_node = Node(data)
        # 이전값 다음이 마지막 꼬리일때
        if prev_node.next is self.tail:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node
        # 꼬리가 아니면
        else:
            new_node.prev = prev_node  # 추가할 노드의 이전 값을 이전 노드 설정
            new_node.next = prev_node.next  # 추가할 노드의 다음 노드를 이전 노드의 next
            prev_node.next.prev = new_node  # 이전노드의 다음이었던 노드의 이전값을 추가할 노드로 설정
            prev_node.next = new_node  # 이전 노드의 다음을 새 노드로 설정

    # 가장 앞에 추가 (insert_after, append는 head에 추가 불가)
    def prepend(self, data):
        new_node = Node(data)
        # 리스트에 값이 하나도 없을때

        if self.head is None:
            self.tail = new_node
        else:
            new_node.next = self.head  # 새 노드의 다음을 기존 head로 설정
            self.head.prev = new_node  # 기존 헤드의 이전을 새 노드로 설정
        self.head = new_node  # 새로운 노드를 new head로 설정

    # 삭제
    def delete(self, delete_node):
        data = delete_node.data
        # case 1. 지우려는 노드가 1개일떄 (tail head)
        # case 2. 지우려는 노드가 tail일때
        # case 3. 지우려는 노드가 head일때
        # case 4. 지우려는 노드가 head or tail 도 아닌 중간 노드일떄
        if self.head is self.tail:
            self.head = None
            self.tail = None
        elif delete_node is self.tail:
            self.tail = delete_node.prev
            self.tail.next = None
        elif delete_node is self.head:
            self.head = delete_node.next
            self.head.prev = None
        else:
            delete_node.prev.next = delete_node.next
            delete_node.next.prev = delete_node.prev

        return data