자료구조 시간에 배운 내용. 프로젝트를 하다보면서 개발을 하다보면서 하나하나 어렴풋해진 이러한 자료구조를 주기적으로 볼 수 있게끔 블로그에 정리해두어야 할 필요가 있겠다고 생각했다.
우선 첫 번째가 리스트(List)이다.
리스트의 정의는 "도표 또는 목록을 추상화 한 것"
(추상화 이런 단어가 썩 내키지 않지만, 이미 정의에서 조차 추상화라는 단어는 좋지 않은 것 같다.)
간단히 말하면 "그냥 자료를 나열해 놓은 것"이라고 정리하고 싶다.
리스트를 표현하는 자체는 크게 배열과 연결 리스트라고 한다.
리스트를 배열로 표현할 때의 장점과 단점, 연결 리스트로 표현할 때의 장점과 단점을 알아야 할 것같다.
한 가지 확실한 것은 배열이 좋다, 연결 리스트가 좋다라고 단정 할 수 없다는 것이다.
리스트를 배열로 표현 했을 때
장점 :
(1) 검색이 쉽고 빠르다.
단점 :
(1) 삽입, 삭제가 용이하지 않다.
(2) 자료의 크기를 가늠할 수 없어 충분히 크게 잡으면 메모리의 낭비를 초래할 수있다.
리스트를 연결리스트로 표현 했을 때
장점 :
(1) 삽입, 삭제가 용이하다.
(2) 자료를 동적인 메모리 공간에 할당하므로 메모리의 낭비를 줄일 수 있다.
단점 :
(1) 단 번에 접근하여 검색 할 수 없다. 처음부터 원하는 데이터가 나올 때까지 연결고리를 이용해 찾아들어야 간다.
왜 그런지에 대해서 그림으로 설명 할 필요가 있겠다.
[배열]
검색이 쉽고 빠르다
우선 배열은 배열의 각 원소가 정해진 크기를 가진다.
간단하게 말해서 물리적으로 동일한 주소크기만큼을 가지고 있다.
그래서 인덱스를 통해서 단 한방에 접근이 가능하다. => 결국 D 라는 데이터에 접근하기 위해서는 [3]로 바로 접근이 가능하다는 얘기다.
무척이나 빠르다는 말!
삽입삭제가 쉽지 않다.?
다음과 같은 경우에 Z라는 값을 배열로 구성된 리스트에 삽입하기 위해서는 해당 자리에 값을 넣고
기존의 있던 3~5까지를 한 번 뒤로 밀어야 한다.
X는 3이라는 인덱스를 갖게 되고 D는 4, E는 5, F는 6
한 번 삽입하는데 시간과 자원의 낭비라고 생각하지 않는가?
[연결리스트]
검색이 오래 걸린다?
연결리스트는 구조가 그 값을 가지는 데이터와 연결 될 주소값을 가지는 데이터로 구성되는 노드(Node) 형태로 존재한다.
여기서 한 가지 알고 가야될 꺼는 다음의 데이터로 연결되는 주소들이 일정하지 않고 그 값을 알 수 없다는 것이다.
D를 검색하기 위해서는 A부터 시작해서 B를 지나 C를 지나 D에 도달해야만 된다는 것이다!
이 것은 단번에 접근가능한 배열에 비해 심한 낭비 일 수 있다.
삽입 삭제가 빠르다?
N이라는 값을 B다음에 삽입하고 싶으면 다음과 같이 하면 된다.
기존에 연결되어있던 B->C의 연결을 끊고 B->N으로 연결하고, N->C로 연결하면 끝이다.
C라는 값을 삭제하고 싶으면 다음과 같이 하면 된다.
기존에 연결되어 있던 B->C와 C->D를 끊고 B->D로 연결해버리면 된다. C++과 같은 경우에 할당된 C의 값을 가진 노드를 할당해제해주면된다.
너무 간편하다. 배열처럼 원하는 자리에 넣고 원소들의 값을 뒤로 밀거나 앞으로 땡길 필요가 없다.
