2019. 11. 15. 16:06ㆍ🔴 ETC
자료구조(Data Structure)는 데이터를 표현하는 방법 및 구조를 뜻한다.
그리고 알고리즘은 데이터를 처리하는 방법을 뜻하는데,
알맞는 자료구조를 선택하면 보다 효율적인 알고리즘을 사용할 수 있게 되는 것이다.
<자료 구조를 전체적으로 분류한 표>
여기서는 선형구조와 비선형구조를 알아볼 것이다!
처음에는 이해하기 어려워도 외운다는 생각보다는
우리 생활에서 일어나는 예시를 생각하면서 보면
더 쉽고빠르게 자료구조를 이해할 수 있게 된다.
1. 선형구조
선형구조는 데이터가 연속적으로 연결되어 있는 모양을 띄고있다.
리스트(List) : 나열할 목록, 나열한 값들 간에 순서를 가지고 있는 리스트
메모리에 저장하는 방식에 따라 나누어짐 :
1) 순차리스트/선형리스트 - 배열(Arrays)
- 특징 :
- <인덱스> <데이터> 로 구성되어있음
- 생성할 때 배열의 크기를 정함
- 데이터 저장되는 순서 = 데이터가 나열된 순서 (논리적 저장순서 = 물리적 저장순서)
- (+) 인덱스를 알고 있으면 해당 원소에 접근할 수 있음
- (+) 저장효율이 뛰어남
- (-) 추가, 삭제는 작업을 완료 후 비어있는 공간을 메꾸기위 한칸 씩 당겨야하기(shift) 때문에 속도가 느림
2) 연결리스트(Linked List)
마치 이어달리기를 할 때처럼 노드에서 포인터가 옆에 있는 노드를 연결해준다
배열의 shift문제를 해결하기 위해 나온 Linked List!
원소들은 자기 옆에 어떤 원소 있는지만 알고 있다
그래서 삭제와 삽입을 shift없이 바로바로 해줄 수 있다
- 특징 :
- 배열과 달리 노드를 통해 포인터를 이용해서 연결된 구조
- 데이터가 들어올때마다 동적으로 메모리를 할당함 (노드 속 한 링크당 4byte, 링크 = 화살표)
- (+) 삽입, 삭제가 용이함
- (-) 논리적 저장 순서와 물리적 저장 순서가 다르기 때문에 데이터 찾는 속도가 느림 (접근속도가 느림)
저장할 원소들의 사이즈를 알고 있다면 Array를 사용하는 것이 좋다,
하지만 삭제/삽입이 활발히 일어나야 한다면 Linked List가 편리하다
그 외 : 스택과 큐는 메모리 안에 있는 데이터들을
좀 더 효율적으로 다루기 위해 만들어진 데이터 참조방식이다
3) 스택(Stack)
책들이 쌓여있다
위에 있는 책부터 꺼내서 보는것처럼 스택은 위에 있는 데이터를 넣고, 뺄 수 있다
맨 처음 쌓은 책 (=맨 아래의 책) -> 제일 마지막에 꺼낼 수 있음
스택을 사용하면 제일 위에 있는 데이터만 알 수 있을 뿐, 아래에 어떤 데이터가 있는 지 알 수 없다
따라서 스택은 데이터를 쌓을 때 의미를 가지는 자료구조이다
- 특징 :
- LIFO (Last In First Out) = 후입선출
- 자료의 입출력이 한 방향으로 제한되어 있음
- 메소드 : push (자료입력), pop(자료빼기), top/peek(최상위 데이터 보기)
- 대표적인 사용 사례 : 실행취소(ctrl+z), 웹브라우저 뒤로가기, 계산기
4) 큐(Queue)
줄을 서서 입장할 때 먼저 줄을 선 사람이 먼저 입장할 수 있는 것처럼
큐는 먼저 입력한 데이터를 먼저 뺄 수 있다
Linked List를 이용해서 큐를 구현하면 큐의 크기를 미리 정하지 않아도 되고
끝에 요소를 추가하기 쉽다는 장점을 가지고 있다
- 특징 :
- LIFO (Last In First Out) = 선입선출
- 자료의 입출력이 한쪽 끝으로 제한되어 있음
- 메소드 : add(데이터를 추가), remove(리스트의 첫번째 데이터 빼기), peek(최상위 데이터 보기)
- 대표적인 사용 사례 : 입출력, 프린터 대기열, 게임 대기열, 버퍼
다음 게시물은 '비선형 구조'를 소개하겠습니다