TIL_Array와 LinkedList(Algorithm)

Array와 Linked List에 대해 정리해 보았다.

 

Array 

접근 쉬움, 삽입 어려움, Python의 list.

특정 원소 조회: O(1)

중간에 삽입, 삭제: O(N)

공간이 다 차면 새로운 메모리 공간을 할당받아야 함

 

LinkedList 

접근 어려움, 삽입 쉬움, 직접 구현.

특정 원소 조회: O(N)

중간에 삽입, 삭제: O(1)

공간이 다 찼어도 맨 뒤의 node만 동적을 추가하면 됨

 

결론

데이터에 접근하는 경우가 빈번할 때는 Array, 삽입과 삭제가 빈번하다면 LinkedList 사용.

 

LinkedList의 구현 code

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)


lst = [1, 2, 3]
l1 = LinkedList()
for e in lst:
    l1.append(e)
print(l1)

구현 코드에서 'print(l1)'에 break point를 걸고 debug를 해보면 list data가 linkedList 형태로 저장되어 있는 것을 확인 할 수 있다.

 

난이도가 좀 있다. 알고리즘을 잘 하기 위해서 정말 꾸준한 연습이 필요할 것 같다.