[패스트캠퍼스 :: 코딩테스트 인강] 2주차 ② 연결리스트/더블 링크드리스트

알고리즘/기술면접 완전 정복 올인원 패키지 Online

 

14. 링크드 리스트 (Linked List) - 4

15. 시간 복잡도 - 알고리즘 복잡도 표현 방법 - 1

16. 시간 복잡도 - 알고리즘 복잡도 표현 방법 - 2

---

시간 복잡도 강의

지난 강의에서 연결 리스트의 기본적인 개념과 구현 방식을 알아보았다면, 이번 시간에는 연결 리스트의 '기본 구조'가 아닌 파생된, 연결 리스트 기본 구조의 단점을 보완한 구조인 더블 링크드 리스트에 대하여 배우게 되었다.

 

자료구조를 공부하면서 처음 들어보는 구조였기에 신기하기도 했고, 확실히 연결리스트의 단점이었던 특정 데이터 노드를 검색하고 찾을 때 무조건 head 데이터인 첫 데이터를 찾아야 하고, 그를 시작으로 모든 노드의 데이터를 거치면서 찾아야 하는 단점을 보완할 수 있는 구조다.

 

또한, 앞서 학습한 배열, 스택, 큐, 연결리스트에서는 크게 중요하게 작용하지 않았던 '시간 복잡도'에 관한 강의를 추가로 학습했다. 

 

보통 책에서는 1장에서 나오는 주제이거나 별첨으로 추가되는 내용인데 강의 목록을 봤을 때도 의아했다.

 

아니나 다를까 강사님께서도 이렇게 중간에 넣은 이유를 설명해 주셨다.

 

 

 

---

1. 더블 연결리스트/링크드 리스트

 

Double Linked List

 

- 더블 링크드 리스트 / 이중 연결 리스트

- 양방향으로 연결되어 있어서 노드 탐색이 양쪽으로 모두 가능

- head, data, next + tail, prev

 

<이중 연결리스트를 구현하고 중간에 위치한 노드 사이에 새로운 노드 삽입 코드 구현>

class Node:
    def __init__(self, data, prev=None, next=None):
        self.prev = prev
        self.data = data
        self.next = next

class NodeMgmt:
    def __init__(self, data):
        self.head = Node(data)
        self.tail = self.head

    def insert(self, data):
        if self.head == None:
            self.head = Node(data)
            self.tail = self.head
        else:
            node = self.head
            while node.next:
                node = node.next
            new = Node(data)
            node.next = new
            new.prev = node
            self.tail = new

    def desc(self):
        node = self.head
        while node:
            print (node.data)
            node = node.next

 

 

2. 시간 복잡도

시간 복잡도

• O(입력)

  • 입력 n 에 따라 결정되는 시간 복잡도 함수
  • O(1), O(𝑙𝑜𝑔𝑛logn), O(n), O(n𝑙𝑜𝑔𝑛logn), O(𝑛2n2), O(2𝑛2n), O(n!)등으로 표기함
  • 입력 n 의 크기에 따라 기하급수적으로 시간 복잡도가 늘어날 수 있음
    • O(1) < O(𝑙𝑜𝑔𝑛logn) < O(n) < O(n𝑙𝑜𝑔𝑛logn) < O(𝑛2n2) < O(2𝑛2n) < O(n!)
      • 참고: log n의 베이스는 2 - 𝑙𝑜𝑔2𝑛log2n

• 단순하게 입력 n에 따라, 몇 번 실행이 되는지를 계산

 

---

시간 복잡도에 대하여 잘 안다고 생각했던 부분도 강의를 들으니 새롭게 느껴지는 것은 왜일까...

 

앞으로의 자료구조에서는 시간 복잡도에 따라 효율적으로 개선하는 방식도 학습이 필요할 것 같다.

이제 진짜 자료구조 시작이다.

 

 

 

[패스트캠퍼스 100% 환급 챌린지 미션 중입니다.]

 

알고리즘 / 기술면접 완전 정복 올인원 패키지 Online. | 패스트캠퍼스