[Python] Array & LinkedList

연결리스트, 스택, 큐, 해시테이블, 힙 → 파이썬의 베이직 자료구조 5인방

자료구조는 알고리즘을 효율적으로 구현하기 위한 기초 체력이므로 제대로 공부해 봅니다.

---

 

Array vs. Linked LIst

 

 

• Array : 파이썬의 리스트. 접근 쉬움, 삽입 어려움. (파이썬의 리스트)
• LinkedList (연결리스트) : 직접 구현. 접근 어려움, 삽입 쉬움.

 

	Array	LinkedList
특정 원소 조회	O(1)	O(N)
중간에 삽입 삭제	O(N)	O(1)
데이터 추가	데이터 추가 시 공간이 다 차버렸다면 새로운 메모리 공간을 할당받아야 한다.	공간이 다 찼어도 맨 뒤의 노드만 동적으로 추가하면 된다.
정리	데이터에 접근하는 경우가 빈번하면 Array 사용	삽입과 삭제가 빈번하면 LinkedList를 사용

 

 

 

연결리스트 구현 ▽

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, val):
        if not self.head:
            self.head = ListNode(val, None)
            return

        node = self.head
        while node.next:
            node = node.next

        node.next = ListNode(val, None)