• 자료구조(Data Structure)

    2023. 3. 23.

    by. JJo 😊

    📌 자료구조(Data Structure)란?

    • 자료구조는 다수의 자료를 담기 위한 구조이다.
    • 데이터의 수가 많아질수록 효율적인 자료구조가 필요하다.

    👀 자료구조의 필요성

    • 데이터를 효과적으로 저장하고 처리하는 방법에 대해 이해해야 한다.
    • 자료구조를 제대로 이해하지 못하면 불필요하게 메모리와 계산을 낭비할 여지가 있다.

    👀 자료구조의 종류

    1. 선형 구조

    하나의 데이터 뒤에 다른 데이터가 하나 존재하는 자료구조이다.
    데이터가 일렬로 연속적으로(순차적으로) 연결되어 있다.

    • 배열(array)
    • 연결리스트(linked list)
    • 스택(stack)
    • 큐(queue)

    2. 비선형 구조

    하나의 데이터 뒤에 다른 데이터가 여러 개 올 수 있는 자료구조이다.
    데이터가 일직선상으로 연결되어 있지 않아도 된다.

    • 트리(tree)
    • 그래프(graph)

    📌 배열과 리스트

    배열(array)

    • 가장 기본적인 자료구조이다.
    • 여러 개의 변수를 담는 공간이다.
    • 인덱스가 존재하며 인덱스는 0부터 시작한다.
    • 컴퓨터 메모리 공간에서 연속적으로 할당된다.
    • 특정한 인덱스에 직접적으로 접근 가능하다 -> 시간복잡도 O(1)

    연결리스트(linked list)

    • 각 노드가 한 줄로 연결되어 있는 자료구조이다.
    • 각 노드는 (데이터, 포인터) 형태를 가진다.
    • 컴퓨터의 메모리상에서 주소가 연속적이지 않다.
    • 리스트의 크기는 동적으로 변경 가능하다.
    • 포인터는 다음 노드의 메모리 주소를 가르킨다. 이를 이용해 삽입과 삭제가 간편하다.(연결성)
    • 특정 번째의 원소를 검색 시, 인덱스가 없으므로 순차적으로 원소를 찾아야 하기 때문에 검색 속도가 느리다. -> 시간복잡도 O(N)
    728x90

    '컴퓨터 공학 지식 > 자료구조, 알고리즘' 카테고리의 다른 글

    퀵 정렬(Quick Sort)  (0) 2023.10.16
    병합 정렬(Merge Sort)  (0) 2023.10.16
    삽입 정렬(Insertion Sort)  (0) 2023.02.21
    에라토스테네스의 체  (0) 2023.02.17
    선택 정렬 (Selection Sort)  (2) 2023.02.16

    댓글