[대충 쓰는 컴퓨터 자료구조 - 개론] http://www.dogdrip.net/43805214

사실 얼마만에 쓰는건지 모르겠다.

방학시즌이 돌아왔으니 다시 달려야지...

이번에 소개할 자료구조는 리스트!

그럼 리스트가 실생활에서는 뭔지 생각해보자.

그리고 사전에서도 찾아보자.

그러하다...

(어? 사전에 내가 설명하려던게 있다...)

컴퓨터에서의 리스트도 실생활에서의 리스트와 똑같다!

무엇인가를 순차적으로 저장할때 사용함.

대신 각 데이터들마다 순차적인 번호가 부여되어있지.

또한 리스트는 중간의 방이 절대로 비어있어서는 안되!

우선 컴퓨터에서 사용하려는 리스트의 정의(?)이지..

그럼 이 리스트를 컴퓨터 메모리상에서 어떻게 표현을 해야하는지 알아보자고?

리스트는 연속된 표현과 연결된 표현 이렇게 두가지로 볼수 있어.

잠깐 다른 이야기로 가볼까?

연속된 표현은 우리가 쓰는 컴퓨터 메모리와 똑같은 구조를 가지고 있지

245번지의 데이터가 뭐야?라고 물으면 100이 들어있어! 라고 가져다주는 형태.

그래서 사실상 연속된 표현의 경우 따로 우리가 해야할일은 없지.

단, 연결된 표현이 문제 인데, 왜 문제이냐면?

1차원 선형 공간인 메모리에서 어떻게 표현할거야?

그렇다. 모든 자료들은 1차원 선형 공간으로 표현할수 있어야되

고로 연결된 표현의 리스트를 어떻게 표현하는지 알려줄거야

다시 돌아와서 연속된 표현의 리스트는

필요한 호텔의 방을 필요한 만큼 미리 예약후 채워나가는방식

근데 예약을 하게 되면 방의 갯수는 절대로 바꿀수 없어.

연결된 표현의 리스트는

호텔에서 방이 필요하면 필요할때마다 방을 잡는방식

근데 방을 직접 찾아 갈순 없고 각 방마다 다음 호실이 적힌 문을 보고 가야되

이제 두가지 리스트의 연산의 종류를 확인해 보자!

<연속표현과 연결표현>

자 그럼 두가지 표현이 있으면 뭐가 더 좋은걸까?

사실 자료구조에 있어서 어떤게 좋고 나쁘고 한건 없음.

그러니 용도에 맞게 쓸수 있게 어떤 장단점이 있는지 보자.

우선 연속된 표현의 최대 장점은 데이터의 탐색이나 데이터의 직접 접근에 있어서 빠른 성능을 보인다는거야.

연속된 표현의 한계는 데이터를 중간에 삭제하거나 중간에 넣어버리면 나쁜 성능을 보여줘.

당연한 이야기지만 예약된 방의 크기가 부족하면 데이터를 더이상 추가 할수가 없다.

자 이제 아래 사진을 보면서 왜 나쁘고 왜 좋은지를 보자.

<연속된 표현의 데이터 접근>

연속된 표현의 직접 접근 방법. 그냥 해당  호실을 기준으로 몇번째 호실에 있나를 계산해버리면됨.

그래서 한번의 연산으로 접근이 가능하지.

<연속된 표현의 삭제>

연속된 표현은 추가/삭제에서 나쁜 성능을 보여주는이유야

"어? 그냥 저 방을 비워 두면 안되?"

리스트의 정의중 리스트는 중간의 방이 비어있으면 안된다는 정의에 어긋나지.

이 정의를 맞춰주기 위해서 비어있는 공간으로 모든 데이터를 하나씩 하나씩 이동을해.

근데 예외가 하나 있어.

만약 맨뒤에서 삭제가 된다면?

어 그냥 그거 지우면되.

또 질문이 있겠지

"어? 그냥 통째로 이동해버리면안되?"

어... 안되.. 컴퓨터에서는 그게 안되.. SIMD(몰라도됨) 명령을 쓰지 않는이상...

(근데 SIMD도 한계가 있는데... 하나씩 옮기는걸 4개 8개로 늘려준다는거?)

<연속된 표현의 삽입>

어 이것도 삭제랑 비슷해

중간에 데이터가 끼어 들어가야 하기 때문에

데이터를 한칸씩 밀어주고 중간에 넣어줘야되.

역시 좀 빠르게 하고 싶다면 SSE나 MMX같은 CPU에서 제공하는 SIMD명령어를 써야지..

(위에서도 말했지만 SIMD도 한계가 존재함..)

역시 여기도 예외가 있어.

공간이 어느정도 있고 뒤에서 삽입이 일어난다면?

어.. 그냥 넣으면되...

<연속된 표현의 오버플로우>

(헉! 옵플... 이거 닉 언급인가..?)

더 이상 원소가 들어갈 공간이 없어.

그래도 넣고 싶다면 새로운 공간을 요구하고

새로운 공간에 데이터를 싹다 복사해줘야지.

<연결된 표현의 삭제>

연결된 표현의 경우 중간에서 삭제가 되는경우.

꼭 필요한 연산이 있어.

바로 탐색이야. 왜냐하면 연결된 표현은 항상 해당 위치로 꼬리를 물어가면서 찾아가야되

마치 다음 힌트를 보고 다음 관문을 찾아가듯이..?

생각해보면

"어? ㅅㅂ 저거 종나 꾸진 자료구조 아니냐?"

단, 연속된 표현과 다르게 자료의 이동연산이 없다.

그저 A는 C가 살던 호실을 지우고, D가 살고 있는 호실로만 기록하면되.

<연결된 표현의 삽입>

삭제와 동일

단, 방을 예약을 받고 호실을 바꿔주는 작업만 하면된다.

<연결된 표현의 탐색>

유일한 단점.

왜냐고? 원하는 번호의 방이 나올때까지 저 꼬리표를 따라가야됨.

자 이제 두가지 리스트를 소개를 했어

자 이제 결론을 내려보자.

1. 리스트는 연속된 표현의 리스트, 연결된 표현의 리스트 두 가지가 있다.

2. 모든 자료구조가 그렇듯이 저 두가지 방식에도 트레이드 오프를 생각해봐야된다.

3. 데이터 변화가 별로 없음 -> 연속표현

4. 데이터의 변화가 심함 -> 연결된 표현이 적합.

<빅오로 표현한 성능>

만약 더 심화된 내용을 보고 싶다면

아래 링크에 있는 맨뒤에 잇는 번외편을 보면 될듯..

http://www.slideshare.net/SamuelLee33/ss-49745117

이 다음은 트리다! 흐흐흫...

아 등판 안할라 그랬는데 사실 catdrip.net 도메인 내가 등록한거... ㅋㅋㅋ