[그림으로 배우는 자료구조] 연결 리스트란?

[그림으로 배우는 자료구조] 연결 리스트란?

 

이번 시간에는 연결 리스트에 대해서 학습해봅시다.

 

학자들은 변수를 많이 만들어 사용하는 대신에 하나의 배열을 선언해서 같은 종류의 많은 양의 데이터를 그룹핑해서 작업을 했습니다.

 

그런데 문제가 발생했습니다.

 

배열 안의 데이터 개수가 많아 질수록 특정 요소를 삭제하거나 특정 위치에 요소를 삽입 할때 기존의 요소들이 이동되면서 오버헤드가 점점 심해졌기 때문입니다.

 

예를 들어 숫자 종류만 담을 수 있는 배열에 숫자가 1,000개가 있다고 가정하면, 이 배열에 존재하는 특정 숫자를 삭제하거나 다른 숫자를 특정 위치에 삽입할때 수백개의 요소가 이동을 해야합니다.

 

학자들은 어떻게 하면 배열의 단점을 보완할지 고민을 했습니다.

고민 끝에 학자들은 연결 리스트라는 자료구조를 만들었습니다.

 

연결 리스트는 데이터 필드와 포인터 필드가 한 쌍으로 구성되어 있고, 일반적으로 데이터 필드와 포인터 필드를 합쳐서 노드(node)라고 부릅니다.

 

노드(node)의 데이터 필드에는 값이 저장되고 포인터 필드는 다음 노드(node)가 저장되어 있는 메모리 주소를 저장합니다. 이 주소를 이용하여 자신의 다음 노드(node)를 찾습니다.

 

 

연결 리스트는 각각의 노드(node)들이 메모리의 여러 공간에 흩어져 있습니다.

 

 

노드들은 메모리상에 각각 떨어진 공간에 존재하기 때문에 특정 데이터를 찾기 위해서는 포인터를 이용해서 첫번째 노드부터 순서대로 따라가야지만 원하는 데이터를 찾을 수 있습니다. 한마디로 검색이 느립니다.

 

 

장점도 있습니다. 배열의 단점을 보완한 부분인데 연결 리스트의 특정 위치에 노드를 추가할때는 해당 노드 앞뒤의 포인터만 변경해주면 됩니다.

 

 

삭제도 마찬가지로 특정 위치의 노드를 삭제한 다음 해당 위치 앞뒤의 포인터만 수정해주면 됩니다.

 

 

배열의 장점은 index 값을 이용해서 데이터에 빠르게 접근이 가능하다는것이고, 단점은 크기가 고정적이고, 특정 위치에 데이터를 삽입하거나 특정 위치의 데이터를 삭제할때 오버헤드가 발생해서 처리가 느리다는 점입니다.

 

연결 리스트의 장점은 데이터를 삽입하거나 삭제할 때 속도가 빠르다는 점이고, 단점은 자신의 다음 노드의 주소값을 저장할 공간이 추가로 필요하다는 점과 검색 속도가 느리다는 점입니다.

 

 

참고

코딩퀴즈 - ios

https://apps.apple.com/kr/app/%EC%BD%94%EB%94%A9%ED%80%B4%EC%A6%88/id1625309702

 

코딩퀴즈 - aos

https://play.google.com/store/apps/details?id=com.codingquiz.myapplication