반항아맛우유

컴퓨터 알고리즘 강의를 연재해볼까 합니다. 

알고리즘을 학습하기 위해서 컴퓨터 자료구조에 대해서 알아야 하는데요. 

그래서 그 중 첫번째인 리스트(LIST)에 대해서 알려드리겠습니다.

<LIST 소개>

우선 리스트에 대해서 짧게 소개하자면.. 정의되지 않은 갯수의 데이터를 관리하기 위해서 리스트를 사용합니다.

일상생활에서보면 일렬로 줄을 세워놓은거라고 보면 됩니다.  일렬로 줄을 세울 때 앞사람이 누군지 확인하고 때에 따라선 뒷사람이 누군지까지 알고 있는거라고 보시면 되고 이런 구조로 데이터를 관리하는겁니다.

리스트와 비교하게 되는 것이 바로 배열인데요. 배열은 정적으로 선언되는 반면에 리스트는 동적으로 관리 할 수 있습니다.

<LIST 예>

그냥 간단한 예로 무한도전을 들도록 하겠습니다. 무한도전은 원래 6명이었죠.. 그래서 프로그래밍을 할 때 6으로 정적으로 선언을 했다면 노홍철, 길, 전진, 광희 등의 영입과 사건사고로 인해서 멤버에서 빠져나가는걸 예상할 수 없었기에 나중에 다시 수정을 해야하는 문제가 발생됩니다. 하지만 리스트로 작성이 되었다면 멤버 추가에 대한 부분이나, 탈퇴에 대한 부분이 쉽게 가능하기 때문에 배열과의 차이가 있습니다.

물론 배열로 무조건 공간을 크게 잡아도 되긴 하지만.. 메모리효율의 문제가 되고 얼마나 큰 공간을 할 당하냐의 문제가 발생하게 됩니다. 핸드폰의 주소록의 예를 들면 얼마의 사람들이 입력하게 될지 입력하기 전까지는 알 수가 없습니다.

하지만! 배열이 무조건 나쁜건 아닙니다. 

배열은 정적이기 때문에 임의 접근이 가능합니다. 그래서 데이터에 접근하기 위해서 리스트보다 빠르게 접근 할 수 있는 장점이 있습니다. 이 말의 뜻은 배열은 인덱스로 구분됩니다. 그래서 인덱스로 접근을 하게 되면 빠르게 데이터에 접근해서 값을 얻어 올 수 있게됩니다.

리스트가 사용되는 때는 데이터의 삽입과 삭제가 많이 이뤄지고, 검색이 많이 이뤄지지 않은 데이터를 관리할 때 유용합니다.

리스트는 스택, 큐, 트리와 같은 자료구조를 이해하는데 중요한 기반을 합니다. 그러니 리스트를 제대로 알고 넘어가시기 바랍니다. 또한 입사 면접에서도 많은 질의가 있으니 충분히 이해하는걸 추천합니다.

리스트를 이해하기 위해서는 기본적으로 C언어의 포인터(*) 의 개념을 알고 있어야 합니다.

포인터를 모르고 리스트를 이해한다는건 조금 어려울수 있습니다. 그러니 리스트 학습전에 꼭 C언어의 포인터를 학습하시기 바랍니다.

<포인터의 간단 설명>

간단하게 포인터에 대해서 소개하자면...포인터는 컴퓨터의 주소값을 저장하는 메모리 공간이라고 소개 할 수 있겠네요. 말이 어려워서 포인터에 대해서 잘 이해 못하는 분들이 많을 텐데요..

포인터는 간단하게 화살표(-->) 라고 보시면 됩니다. 화살표는 정확하게 한곳을 가리키는 위치가 있습니다. 이것만 우선 알고 계시면 리스트를 이해하는데 어려움은 없을겁니다. 메모리 할당, 힙영역 이런게 있겠지만.. 우선 깊은건 패스하겠습니다.

리스트에서 사용되는 용어가 있습니다. 바로 노트(Node), 헤드(Head), 테일(Tail) 이렇게 3가지가 있는데요. 

리스트 내의 각 요소를 노드(Node)라고 부릅니다. 

그냥 학자들이 이렇게 부르기로 약속하고 정의한거니까 알고 넘어가시면 됩니다. 이렇게 부르면 왠지 유식해 보이고 뭔가 아는듯해 보이잖아요~ 그럼 앞으로 폼나게 노드라고 불러봅시다~ 그리고 헤드(Head)는 제일 앞에 있는 노드를 부를때 사용되고, 당연히 테일(Tail) 마지막 노드를 지칭하게 됩니다.

위 사진에서 보면 유재석이 헤드, 정준하가 테일이라고 할 수 있습니다.

리스트의 종류에는 3가지가 있습니다.

1. 단일 링크드 리스트 (Single Linked List)

단일링크드리스트는 한방향으로 노드를 가리키게 됩니다. 위에 예를 들면 유재석은 박명수를 기억하고 있고 박명수는 정형돈만 기억하는 방식입니다. 예전에 조회시간에 줄을 세웠을 때 앞사람이 누군지만 확인하라는 선생님의 말과 비슷하다고 보면 됩니다. 뒷사람은 누군지 모르는거죠~

2. 더블 링크드 리스트 (Double Linked List)

이중링크드리스트는 단일 링크드 리스트에서 한개거 더 추가된겁니다. 유재석은 박명수를 알고, 박명수는 유재석, 정형돈을 모두 알고 있는 겁니다. . 줄을 세울때 앞뒤 사람을 알고 있는거랑 같은거라고 보면 됩니다. 이로써 정형돈에서 앞사람, 앞사람으로 탐색을 할 수도 있고 뒷사람, 뒷사람... 으로 탐색을 할 수 있게 됩니다.

3. 환형 링크드 리스트 (Circular Linked List)

환형링크드리스트는 더블링크드리스트와 비슷하지만~ 1가지가 다른데요.. 바로 헤더와 테일이 서로를 가리키고 있습니다. 이로써 일렬로 줄을 서는게 아니라 원형으로 둥글게 손을 잡고 강강술레를 하는거 같은 구조가 되는겁니다.

3가지 리스트를 다 학습할 필요는 없구요.. 1가지 더블 링크드 리스트만 알면 나머지는 자연스럽게 알게 됩니다. 물론 환형링크드리스트를 알아도 나머지를 알 수 있습니다. 그리고 내용을 알게 되면 자연스럽게 나머지의 장단점을 알게 되실겁니다.

리스트의 장점

1) 정해지지 않은 갯수의 데이터를 동적으로 생성하고 관리 할 수 있음.

2) 데이터의 추가가 쉬움.

3) 데이터의 삭제가 쉬움.

4) 데이터의 삽입이 쉬움.

리스트의 딘점 

1) 데이터의 검색 시 많은 시간이 소요됨. (최악의 경우 데이터의 갯수만큼 검색해야함)

2) 데이터의 갯수를 알기 위해서 데이터갯수 만큼 반복을 해서 카운트 해야함. 데이터가 많을 수록 시간이 오래 소요됨.

간단하게 하려했으나 글이 상당히 길어졌네요... 이만하면 대충 개념적인건 설명은 다했다고 할 수 있겠네요.

그럼 실제 구현에 대해서는 다음 강의로 넘어가도록 하겠습니다.

해당 글에 도움이 되셨다면 공감(하트) 버튼 클릭 부탁드리겠습니다.