TIL#34 자료구조 -1

Dasom·2020년 8월 16일
0

자료구조

목록 보기
2/8

자료구조

데이터의 효율적인 접근 및 조작을 가능하게 해주는 저장 및 관리방식

목적 -> 자료를 구조화하여 데이터를 효율적으로 사용하기 위해


스토리지 : 데이터가 영구적으로 저장되는 곳. 데이터를 저장하고 받아오는데에 오래걸림

메모리 : 데이터가 임시로 저장되는 곳. 데이터를 저장하고 받아오는데에 빠름

RAM : 임의접근 메모리.

임의접근 - 저장 위치를 알면 접근할 때 항상 일정한 시간이 걸림(시간복잡도 O(1))
순차접근 - 저장된 위치까지 가는데 한단계씩 거쳐야 함

-> 임의접근이 순차접근보다 훨씬 효율적


레퍼런스(reference)
데이터에 접근할 수 있게 해주는 값
'주소'보다 조금 더 포괄적인 개념
자료구조를 배울때에는 주소=레퍼런스 라고 생각해도 됨

배열

인덱스 접근 - O(1)
선형탐색(순서대로 탐색하는 것) - O(n)

정적배열
크기 고정(요소수 제한)

동적배열
크기 변함(요소 계속 추가 가능). 정적배열로 만들어진 자료구조. 정적배열의 크기를 상황에 맞게 조절

  • 파이썬 리스트는 동적 배열이며 C배열을 이용해서 동적 배열을 구현(C배열은 정적 배열)

추가 연산 시간 복잡도 : 최고의 경우(내부배열에 빈공간이 있을 때. 자주일어남) O(1), 최악의 경우(내부배열에 빈공간이 없을 때. 가끔 일어남) O(n)

❗️ 분할상환분석 ( 할부라고 생각하면 됨)
시간분석도를 최악의 경우를 얘기하지 않고 평균을 내어 얘기함. 같은 동작을 n번 했을 때 드는 시간이 x일때 -> 동작을 한번 하는데 걸린시간 : x/n

따라서, 동적배열의 추가연산 시간복잡도는 최악의 경우 O(n)이며 분할 상환 분석을 하면 O(1)이 걸린다

삽입연산시간복잡도 : O(n)

삭제연산시간복잡도 : 아무 위치에 있는 데이터를 삭제할 때는 최악의 경우 O(n). 가장 뒤에 있는 데이터를 삭제할 때는 최악의 경우 O(n)이 걸리지만 분할 상환 분석을 적용하면 O(1).

연결리스트(Linked List)

데이터를 순서대로 저장해준다.
요소를 계속 추가할 수 있다.
노드 1개에 데이터값과 다음노드의 주소값이 저장되어 있어서 서로 연결
Head node 만 알면 주소값을 타고 타고 모든 노드들을 알 수 있다.

시간 복잡도 : 접근 O(n) / 탐색 O(n) / 삽입 O(n) / 삭제 O(n)
❗️ 가장앞에 삽입, 가장 앞 노드 삭제, 가장 뒤에 삽입 -> O(1) / 가장 뒤 노드 삭제 O(n)

class Node:
    """링크드 리스트의 노드 클래스"""

    def __init__(self, data):
        self.data = data  # 노드가 저장하는 데이터
        self.next = None  # 다음 노드에 대한 래퍼런스

class LinkedList:
    """링크드 리스트 클래스"""

    def __init__(self):
        self.head = None
        self.tail = None

    def insert_after(self, previous_node, data):
        """링크드 리스트 주어진 노드 뒤 삽입 연산 메소드"""
        new_node = Node(data)

        if previous_node is self.tail:
            self.tail.next = new_node
            self.tail = new_node
        else:
            new_node.next = previous_node.next
            previous_node.next =  new_node
            
    def delete_after(self, previous_node):
        """링크드 리스트 주어진 노드 뒤 삭제 연산 """
        data = previous_node.next.data # 링크 리스트의 데이터를 삭제할때는 지워주는 데이터를 리턴해주는게 관습.

        if previous_node is self.tail:
            previous_node.next = None
            self.tail = previous_node
        else:
            previous_node.next = previous_node.next.next

        return data

    def find_node_at(self, index):
        """링크드 리스트 접근 연산 메소드. 파라미터 인덱스는 항상 있다고 가정"""
        iterator = self.head

        for _ in range(index):
            iterator = iterator.next

        return iterator

    def append(self, data):
        """링크드 리스트 추가 연산 메소드"""
        new_node = Node(data)

        if self.head is None:  # 링크드 리스트가 비어있는 경우
            self.head = new_node
            self.tail = new_node
        else:  # 링크드 리스트가 비어 있지 않은 경우
            self.tail.next = new_node
            self.tail = new_node

    def __str__(self):  # 자동으로 내용을 사람들이 이해할 수 있는 문자열로 리턴해주는 메소드
        """링크드 리스트를 문자열로 표현해서 리턴하는 메소드"""
        res_str = "|"

        iterator = self.head

        while iterator is not None:
            # 각 노드의 데이터를 리턴하는 문자열에 더해준다
            res_str += f" {iterator.data} |"
            iterator = iterator.next # 다음노드로 넘어간다

        return res_str
profile
개발자꿈나무🌲

0개의 댓글