연결리스트란?
사내동아리 지코바에서 주어진 첫 번째 과제.
연결리스트에 대해 연구하라! 알고리즘을 위한 자료구조에 대한 내용을 조사하고,
스스로 의문을 더해 알아보는 시간을 가졌다.
자료같은 경우 방대한 구글의 자료들을 빌려 금방 구할 수 있었지만,
머릿속에 우겨넣는건 생각보다 쉬운 일이 아니었다.
이 글은 내 공부했던 방향대로 쓰여졌다.
연결리스트. 이제 막 개발공부를 시작한 사람으로써 생소한 단어였다.
무작정 구글에 검색했다.
나무위키의 답은 이랬다.
Linked List
추상적 자료형인 리스트를 구현한 자료구조로, Linked List라는 말 그대로 어떤 데이터 덩어리(이하 노드Node)를 저장할 때 그 다음 순서의 자료가 있는 위치를 데이터에 포함시키는 방식으로 자료를 저장한다.
여기서 나는 모르는 단어들을 제외하고 이해를 하도록 노력해봤다.
이해가 잘 안된다. 추상적 자료형인 리스트라는게 감이 잘안왔다. 또한 노드란 단어가 어려워보인다. 하지만 데이터 덩어리라고 지칭을 해주었으니, 우선 자료들을 뭉쳐놓은 느낌을 받았다. 이 부분은 넘어가고 다음을 이해해보자.
그 다음 순서의 자료가 있는 위치를 데이터에 포함시키는 방식으로 자료를 저장
이 부분이 중요한 듯하다. 어떻게 저장하는지에 대한 방법이 나와있다. 느낌상
방법을 알려준 것은 다른 어떤 자료구조와의 차이점이 있는듯한 느낌이다. 연결리
스트는 어떤 자료가 있다면 그 다음 자료의 위치가 있을 것이고, 그 위치에 데이
터를 기억하는 식. (확실하진 않으나 이런느낌이지 않을까? 나중에 확신이 들면
수정해야지...)
내가 그린 사진!!
우선 내가 이해한 연결리스트는 여기까지다. 근데 뭔가 없다. 아무래도 과제를 내주신
지코바 회장님(이하 윤님이라 칭함.)의 글을 보면서 힌트를 얻어야겠다는 생각을 했다.
윤님이 쓰신 글을 몰래 훔쳐보자. (실은 우리들을 위해 조사내용을 정리해주셨다... ㅜ 감동)
자료구조는 우선 선형과 비선형으로 나뉜다. 그리고 선형에는 이것과 저것, 그리고
연결리스트가 있다!
그럼 연결리스트는 자료구조 중 선형을 띈다는 것을 알 수 있었다.
선형? 비선형? 처음듣는 나지만, 느낌상 선으로 연결된거! 선으로 연결이 안된거!!
느낌은 그랬지만 대충 넘어가면 나중에 혼돈이 올 확률이 크니, 확인을 해보자.
역시 느낌대로 갔으면 혼날뻔했다...!
선형. 선으로 연결된 것이 맞다. 비선형? 선으로 연결된게 아니긴하다...
근데... 그림으로 보는게 편하겠다.
그림<2>
그림에서 보이는것과 같이 선형은 진짜 선 하나다.
반면에 비선형은 나무가 가지치는 듯한 모양새를 하고 있다.
큰 차이점은 바로 하나의 자료에 1:1로 대응하는 선형.
그리고 하나의 자료에 여러개가 들어갈 수있는 1: 다수의 비선형. 이것이다.
이정도면 어느정도 전체적인 틀이 잡힌것 같다.
연결리스트란. 자료가 1:1 식으로 대응이 되면서,자료를 순서대로 기억하는게 아
니라, 위치로 기억하는 자료구조를 뜻한다. 우선 여기까지 이해하고 내가 내린 결론이다.
근데, 선형에 대해서 좀 더 이해하기 위해서 구글링을 조금 더해본 결과,
선형에는 진짜 알지도 못하면서 쓰던 배열도 선형에 포함되어 있는걸 봤다...
이제야 드디어 내가 배열을 어떻게 썼는지 알아낸 순간... 그전까진 그냥 때려맞췄다면
이번엔 퍼즐이 풀린느낌 허허 기분이 좋았다.
근데 여기서 의문점이 들었다. 배열이랑 연결리스트랑 차이가 뭘까?
검색을 안해보고 생각을 해보자.
배열? 순서대로 쭉. 연결리스트? 연결되게 쭉...
??? 생각하기엔 너무 늦은시간... 피곤하니 검색하도록하자.
배열과 연결리스트에서 내가 느끼기에 가장 큰 차이점은 바로
배열은 순차적, 연결리스트는 순차적이 아니라는 점.
그림을 한 번 구경해보자.
<그림3>
아.. 그랬다. 배열에서 중간에 있는 무언가를 가져왔을때 인덱스로 가져온 기억이 있다.
그리고 연결리스트를 공부했을때, 위에서 위치로!! 데이터를 기억한다고했다!
느낌이 확 오지 않는가. 이런 구조에서 나오는 배열과 연결리스트의 장단점이 있다.
배열은 쭉 나열이 되어있다. 만약 자료 하나를 삭제하거나 추가를 한다면, 그리고 그 자료가
중간에 있다면 자료의 추가/제거로 인해 배열이 달라질 것이다. 배열이 아예 달라지므로,
아마 데이터가 전부 변경될 것같다 라고 생각했는데, 전부 변경이 된다고 찾을 수 있었다.
반면, 연결리스트는 위치로 기억하기 때문에, 자료가 하나 사라진다고 문제가 될
이유가 없어질 것 같았는데, 역시 없어질 이유가 없다.
적절한 비유가 될진 모르지만 아파트와 주택을 생각했다. 아파트는 배열, 주택은 연결리스트.
처음부터 20층인 아파트가 있다. 집이 비어있어도, 20층을 생각하고 만들었다.
우선 세대수 낭비가 있다!
20층 아파트가 있는데, 중간에 4층을 없애버렸다? 그럼 19층으로 바뀌겠지.
하지만 실제로는 4층이 부서지면 건물 전체가 부서져서 새로 다시 지어야 할 것이다.
이게 배열!!
반면 주택들 여러세대 대충 5세대가 옹기종기 한 마을에 있다.
당씨네 김씨네 이씨네 박씨네 상씨네(엥... 딱 다섯개네..?!)
그리고 살았던 순서는 뭐 지멋대로다. 당씨가 먼저있었고 추가로 상씨가 왔을 수도있고,
김씨랑 이씨가 있는데, 추가로 박씨 상씨, 마지막으로 당씨가 올 수 있지 않는가
어쨌든간에...
서로 다 이웃이다. 그러던 중에 만약 당씨네 집이 이사를 가서 집을 부쉈다? 나머지 4집에는
영향이 안가지않는다. 물론 심적으로는 허전함이 있을 순 있겠지만, 그렇다고 집의 위치가
변경은 되진 않는다! (이 사람들은 심적 허전함에서 공감을 못할듯 당씨니까)
지금까지 연결리스트와 배열의 차이까지 알아봤다. 물론 더 있지만,
동호회 사람들에게 설명해줄때 생각나면 하고, 아니면... 혼날듯...
생각해 내야겠다.
이쯤이면 연결리스트의 기본적인 특징은 얼추 다 나온것같다.
그럼 연결리스트의 종류엔 어떤 것이 있을까.
(찾아볼 생각을 못하고 있었는데, 회장님 글을 보다가 필수로 들어가야할 목록에...)
연결리스트는 4종류로 나뉜다.
단일 연결리스트, 이중 연결리스트, 다중 연결리스트, 원형 연결리스트
단일 연결리스트. 말그대로 하나만!!!
노드(데이터 덩어리 말이 생소해서 데이터 덩어리로 기억해도 좋을듯!)가 다음 노드를 가리킨다!
이중 연결리스트. 말그대로 두개만!! 앞 뒤로 연결되어있다.
즉 노드가 이전노드, 다음노드를 가리킨다.
다중 연결리스트. 이것도 말그대로 여러개가 연결되어있다.
여기서 좀 생소하게 포인트란 단어가 쓰였는데, 단어 그대로 여러개를 가리키기 때문에 이전, 다음이 아닌 직접적으로 가리키는 포인터를 뜻하는 듯하다.
정확하진 않으나, 설명들의 정황상 이렇게 나타내고 있다. 이부분은 동호회에 계신 엄청난 고수 두 분께 맞다 틀리다라는 확답을 들어야겠다.
마지막으로 원형 연결리스트. 둥글게 둥글게 원형으로 생긴 연결리스트~
지구는 둥그니까 결국 제자리로 마지막 노드가 처음 노드와 연결...되어있다.
이정도면 크게 어려운 내용은 없는듯하다!! 이해는 어렵지않게 할 수 있었다!!
물론 이해한 내용이 다 맞다는 가정하에
이제 사용법에 대한 것을 알아봐야겠다. <이미 찾아놨으니, 발표시간에 공유해야디>
