목표
데이터구조 기본 재료
배열
연결리스트
데이터구조 기본재료(단순구조)
컴퓨터 세계에서 프로그래밍을 하는데 사용되는 기본 재료들이 존재한다.
정수, 실수, 문자열, 문자가 존재한다
선형구조와 비선형 구조
자료구조는 크게 선형 구조와 비선형 구조로 나눌 수 있다. 선형 구조는 데이터가 일렬로 연결되어 있는 구조이고 비선형 구조는 자료의 구성이 일렬이 아닌 특정한 형태를 띠는 구조이다.
선형구조로는 대표적으로 배열, 연결리스트, 스택, 큐,덱 등이 있으며, 비선형구조에는 트리, 그래프가 있다.
배열(Array)
일반적인 선형 구조로서 인덱스와 인덱스에 대응하는 데이터들로 이루어진 자료구조이다. 자료값을 나타내는 가장 작은 단위가 자료를 다루는 단위이다.
- 특징
같은 타입의 데이터를 나열한 선형 자료구조
연속된 메모리 공간에 순차적으로 저장
배열의 크기는 고정, 이후 변경할 수 없음
검색이 잦고 삭제 삽입 적은 경우 사용에 용이
- 장점
인덱스를 가지고 있어 탐색에 용이
연속된 메모리 공간에 존재하기 때문에 메모리관리 용이
- 단점
삽입/삭제가 어렵다. (모든원소들을 한칸씩 이동시켜야 한다.)
배열의 크기를 바꿀수 없다. (초기 배열크기를 설정하기 때문에 메모리 공간 낭비 발생)
연결리스트(Linked List)
노드를 단위로 한다. 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조이다. 노드가 가리키는 것이 없으면, 해당 노드가 끝이다.
- 특징
트리를 이용한 검색
데이터는 두고 위치 값(포인터) 로 데이터를 연결한다.
배열(순서가 있는리스트) 보다 검색 속도는 느리지만 삽입/삭제에 용이
연결리스트는 노트로 구성되어 있다.
- 장점
프로그램 수행을 하며 (RunTime) 동적으로 메모리 할당
리스트의 크기가 동적이다. (힙영역 사용)
- 단점
배열에 비해 프로그래밍 복잡하다
인덱스가 없으므로 검색 시 첫 노드부터 노드를 탐색해야 한다.
- 원형 연결리스트 : 각 노드는 다음 노드를 가리키고, 마지막 노드가 처음 노드를 가리키는 연결 리스트이다.
- 이중 연결리스트 : 각 노드는 이전 노드와 다음 노드를 가리키는 참조값으로 구성된다. 처음 노드의 이전 노드와 마지막 노드의 다음 노드는 없다.(NULL)
- 원형 이중 연결리스트 : 처음 노드가 이전 노드로 마지막 노드를 가리키고, 마지막 노드가 다음 노드로 처음 노드를 가리키는 이중 연결 리스트이다.
참조
https://ko.m.wikipedia.org/wiki/자료_구조
자료 구조 - 위키백과, 우리 모두의 백과사전
자료구조(資料構造, 영어: data structure)는 컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미한다.[1][2][3] 더 정확히 말해, 자료 구조는 데이터 값의 모임, 또
ko.m.wikipedia.org
알고리즘 국형준 저
'컴퓨터 > data science' 카테고리의 다른 글
| 알고리즘 기본기 다지기6.기초 데이터구조 (트리) (0) | 2021.08.20 |
|---|---|
| 알고리즘 기본기 다지기5.기초 데이터구조 (집합) (0) | 2021.08.19 |
| 알고리즘 기본기 다지기4.기초 데이터구조 (덱, 우선순위 큐) (0) | 2021.08.18 |
| 알고리즘 기본기 다지기3.기초 데이터구조 (스택, 큐) (0) | 2021.08.16 |
| 알고리즘 기본기 다지기1.데이터구조와 알고리즘 (0) | 2021.05.11 |