자료구조 - List(리스트)와 종류

728x90

자료구조 중 하나인 List는 배열의 한계를 극복할 수 있는 강력한 자료구조 중 하나이며 데이터를 단순하지만 효율적으로 다룰 수 있는 자료구조입니다.

List는 Array처럼 어떠한 데이터들을 묶기위한 개념입니다. 배열과 대표적으로 다른 특징은 아래와 같습니다.

가장 기본적이고 대표적인 자료구조이기 때문에 다양한 언어에서 List의 개념을 적용한 다양한 자료구조들을 제공하고 있는 경우가 많습니다. 본문에서는 이 List의 자료구조의 2가지 종류에 대해서 장단점을 알아보도록 하겠습니다.

위의 List의 개념을 적용시켜 표현하는 대표적인 2가지 부류의 List 자료구조의 종류가 있습니다. 그 2종류의 특징과 개념에 대해서 알아보도록 하겠습니다.

순차 리스트(Sequential List)
- 자료들을 순차적인 메모리공간안에 연속하여 저장되는 자료구조
- 배열과 비슷하나 빈자리 공간이 없이 순서대로 저장이 되는 특징
- 논리적 순서와 물리적 순서가 동일하다
- 탐색에서는 효율적이나 추가,삭제에서는 상대적으로 효율이 떨어진다
연결 리스트(Linked List)
- 자료를 저장하기위해 자료부 분과 위치를 알려주는 노드 부분으로 구성한 자료의 묶음
- 노드 부분을 통해 논리적인 순서로 메모리상에 저장 (논리적 연결이 있을 뿐 메모리상에서 자료들을 연속하여 저장되지 않을 수 있음)
- 추가, 삭제에서 효율적이나 상대적으로 탐색 능력이 떨어진다.

그럼 먼저 순차 리스트를 먼저 알아보도록 하겠습니다. 순차 리스트는 위에서 정리했다시피 물리적 논리적 순서가 동일합니다. 그래서 탐색은 효율적이나 추가 , 삭제 등은 효율이 떨어진다고 말했습니다. 시각화해서 한번 살펴보도록 하겠습니다.

그림처럼 이름을 담는 순차리스트가 있다고 가정한다면 메모리 공간 안에 순서대로 이름이 저장되게 됩니다.

보이는 그대로 물리적, 논리적 순서가 동일합니다. 따라서 탐색또한 순서대로 이루어지게 됩니다.

위의 순차리스트에서 가장 마지막 부분에 데이터를 더 이어 붙이고, 삭제를 하는 것은 문제가 없을 것입니다.

하지만 중간 과정에서 삭제가 이루어 진다면 어떻게 될까요?

순차 리스트를 사용하여 데이터를 삭제하거나 추가한다면 위와 같은 연산이 필요합니다. 중간에 데이터를 삽입 삭제는 가능하지만 데이터를 삽입하는 위치의 뒤의 자료들을 다시 한번 뒤로 밀어주거나 당겨주는 연산을 해야 됩니다.

~~(추후 이 연산이 왜 많이 걸리는지는 정렬 알고리즘 등을 통해 알아보도록 합시다.)~~

데이터를 삭제하거나 중간에 삽입하는 경우가 적다면 해당 개념을 적용한 리스트 자료구조를 사용하는 것이 효과적입니다.

연결 리스트는 물리적인 공간에 순서대로 저장되어 있지 않습니다. 그 대신 각 데이터마다 노드를 만들어 위치정보를 저장합니다. 시각화해서 본다면 다음과 같습니다.

이처럼 연결 리스트의 개념은 서로 각각의 데이터 묶음(노드) 안에 다음 데이터의 위치정보를 함께 저장하면서 이루어집니다. 따라서 연결 리스트는 상대적으로 순차 리스트에 비해 복잡할 수 있습니다.

그림처럼 전체 부분의 수정이 아닌 노드 안에 담긴 위치정보의 변경으로서 자유롭게 연결이 가능합니다.

마지막 노드의 경우 다음 노드가 존재하지 않습니다. 이 때문에 기준 노드처럼 마지막 노드에 대한 정보 또한 저장하고 관리를 해야만 효율적입니다.

이런 식으로 연결 리스트를 사용하면 특정 부분에 데이터를 삭제 삽입하는 과정에서의 연산은 순차 리스트보다 훨씬 효율적인 구조로 이루어집니다.

다만 탐색의 경우에는 계속해서 위치정보 읽고 찾아가며 이동해야 되기 때문에 메모리에서 순서대로 읽는 것과는 차이가 분명합니다.

본문을 통해 리스트의 대표적인 종류 2가지와 특징에 대해서 알아보았습니다.

728x90

Popular Aricle