-
📌 자료구조(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 댓글