[자료구조] 링크드리스트

[자료구조]

자료구조 강의

링크드 리스트

양방향 링크드 리스트

Doubly linked list, 노드가 이전 노드의 주소, 다음 노드의 주소를 가져 양방향으로 연결되어 있기 때문에 노드 탐색이 양쪽으로 모두 가능한 자료구조

• 구현

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: # head 없을 때 head 설정
            self.head = Node(data)
            self.tail = self.head
        else:
            node = self.head # head 부터 돌기 시작
            while node.next: # 마지막까지
                node = node.next
            new = Node(data) # 새로운 Node 만들기
            node.next = new # 현재 노드의 다음 노드는 null이 아니라 새로 만든 Node
            new.prev = node # 새로 만든 노드가 가리키는 이전 노드는 현재 노드
            self.tail = new # 방금 생성한 노드는 가장 맨 마지막 노드이므로 tail 설정

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

    # 처음부터 찾기
    def search_from_head(self, data):
        if self.head == None:
            return False

        node = self.head # head 부터 시작
        while node:
            if node.data == data: # 입력받은 data와 처음부터 찾던 node의 data랑 같으면
                return node # 그 노드 반환
            else:
                node = node.next # 아니면 keep going
        return False # 못 찾았으면 그런 노드 없는거

    # tail 부터 찾기
    def search_from_tail(self, data):
        if self.head == None:
            return False

        node = self.tail
        while node:
            if node.data == data:
                return node
            else:
                node = node.prev # next가 아니라 prev 아래로 keep going
        return False

    # 특정 data 앞에 노드 넣기
    def insert_before(self, data, before_data):
        if self.head == None: # head가 없으면
            self.head = Node(data) # Node 생성해서 head로 추가
            return True
        else:
            node = self.tail # 뒤에서 부터 찾음
            while node.data != before_data: # 넣으려고 하는 위치 데이터와 찾는 노드 데이터 같을 때까지 확인
                node = node.prev
                if node == None:
                    return False
            new = Node(data)
            before_new = node.prev
            before_new.next = new
            new.prev = before_new
            new.next = node
            node.prev = new
            return True

    # 특정 data 뒤에 노드 넣기
    def insert_after(self, data, after_data):
        if self.head == None:
            self.head = Node(data)
            return True
        else:
            node = self.head
            while node.data != after_data:
                node = node.next
                if node == None:
                    return False
            new = Node(data)
            after_new = node.next
            new.next = after_new
            new.prev = node
            node.next = new
            if new.next == None:
                self.tail = new
            return True

데이터를 삽입할 때, 앞 노드의 next와 뒷 노드의 prev 설정을 잊지 말아야 한다.

시간복잡도

1. 알고리즘 복잡도

   다양한 알고리즘 중 어느 알고리즘이 더 좋은지를 분석할 수 있는 지표, 복잡도를 정의하고 계산한다.

• 시간 복잡도: 알고리즘 실행 속도
• 공간 복잡도: 알고리즘이 사용하는 메모리 사이즈 => 시간 복잡도가 중요!

1. 시간 복잡도

시간 복잡도의 주요 요소는 반복문이다.

시간 복잡도에 가장 영향을 많이 미치는 요소, 즉 반복문만 고려하면 된다. (입력의 크기가 커지면 커질수록 반복문이 알고리즘 수행 시간을 지배한다.)

1. 표기법

• Big O (빅오) 표기법:
  O($n$) 알고리즘의 최악의 실행 시간을 표기 가장 일반적으로 많이 사용되는 표기법
  아무리 최악의 상황이더라도 최소한의 성능은 이렇다는 것을 알려주기 때문

1. Big O 표기법의 계산

1) O($n$) 입력 n에 따라 결정되는 시간 복잡도 함수 입력 n의 크기에 따라 시간복잡도가 기하급수적으로 늘어날 수 있다. 가장 큰 영향을 미치는 입력 n의 단위로 표기한다. 2) 시간 복잡도 순서: O($1$) < O($logn$) < O($n$) < O($nlogn$) < O($n^2$) < O($2^n$) < O($n!$)