Array and LinkedList

Array vs LinkedList

상황	Array	LinkedList
특정 원소 조회	O(1)	O(N)
원소 삽입, 삭제	O(N)	O(1)
원소 추가	데이터 추가 시 공간이 찼다면 새로운 메모리를 할당 받아야한다.	모든 공간이 차도 맨뒤에 노드만 동적으로 추가한다.
정리	데이터 조회가 빈번하다면 Array!	삽입과 삭제 또는 데이터 추가가 빈번하다면 LinkedList!

 

*그렇다면 파이썬의 경우 리스트는 링크드 리스트인가?

 pyhton의 리스트는 array로 구현되어 있다. 하지만 append의 경우 내부적으로 동적 배열이라는 걸 사용해서, 배열의 길이가 늘어나도 O(1)의 시간 복잡도가 걸리도록 설계가 되어있다. 

 따라서 python의 배열은 링크드 리스트로 쓸 수 있고, 배열로도 쓸 수 있게 만든 효율적인 자료구조이다.

 

참고 자료

https://stackoverflow.com/a/5932364 

Internals of Python list, access and resizing runtimes

https://en.wikipedia.org/wiki/Dynamic_array

Dynamic array - Wikipedia

 

LinkedList 구현

# Linked List
class Node:
    def __init__(self, data) -> None:
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self, data) -> None:
        self.head = Node(data)

    # 원소 추가 메소드
    def append(self, data):
        if self.head is None: # 헤드가 None일 때, 예외처리
            self.head = Node(data)

        cur = self.head # 노드의 현재 위치
        while cur.next is not None:
            cur = cur.next
        cur.next = Node(data)

    # 원소 출력 메소드
    def print_node(self):
        cur = self.head
        result = []
        while cur is not None:
            result.append(cur.data)
            cur = cur.next

        print(result)

    # index번째 원소 반환
    def get_node(self, index):
        cur = 0
        node = self.head
        while cur != index:
            node = node.next
            cur += 1
        
        return node

    # index번째 원소 추가
    def add_node(self, index, value):
        new_node = Node(value)
        # 0번째 원소가 들어오면, head를 다음으로 옮겨놓고, 헤드 자리에 새로운 노드를 추가
        if not index:  
            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_node

    # index번째 원소 삭제
    def delete_node(self, index):
        if not index:
            self.head = self.head.next
            return

        node = self.get_node(index - 1)
        node.next = node.next.next


# linked list 객체 생성
linked_list = LinkedList(3) 

# append method 확인
linked_list.append(4)
linked_list.append(5)
linked_list.append(6)
linked_list.print_node() 

# get method 확인
print(linked_list.get_node(3).data) 

# add method 확인
linked_list.add_node(0, 2)
linked_list.print_node() 

# delete method 확인
linked_list.delete_node(3)
linked_list.print_node()