[자료구조] 리스트(List)

자료구조 리스트에 대해 알아보자. 우리가 흔히 일상생활에서 사용하는 리스트와 같다.

(EX. 오늘 할 일, 장 볼 리스트 등등)

 

리스트는 순서의 개념이 없는 집합과는 다르게 순서, 위치를 가진다. 스택, 큐 또한 크게 본다면 리스트라고도 볼 수 있다. 리스트는 구현 방법에 따라 배열로 구현하는 순차 리스트, 연결 리스트로 구현하는 여러 연결 리스트들이 있다. 연결 리스트들에는 단일 연결 리스트, 원형 연결 리스트, 이중 연결 리스트가 있다.

리스트 분류

각 리스트들에 대해 대략적으로 알아보자.(각 리스트의 코드적인 부분은 추후 포스팅할 예정)

---

##순차 리스트

순차 리스트는 배열로 구현한 리스트로서 구현이 쉽고 속도가 빠르다는 장점이 있다. 하지만 배열의 특성상 동적으로 크기를 줄이기 어렵다는 단점이 있다.

배열

 

[삽입]

삽입 연산

삽입할 위치 인덱스를 나타내는 변수를 선언하여 원하는 위치에 값을 입력한 뒤 그 뒤에 값들은 한 칸씩 뒤로 미루는 방식이다.

[삭제]

삭제 연산

삭제는 삽입의 반대개념으로 삭제할 위치 인덱스를 나타내는 변수를 선언하여 뒤에 값들을 앞당기는 방식이다.

 

따라서 삽입이나 삭제 연산이 많다면 원소를 직접 옮기는 과정에서 시간이 많이 걸린다.

---

##연결 리스트​

연결 리스트는 크기에 제약을 받지 않고 중간에 쉽게 삽입, 삭제를 할 수 있다는 장점이 있다. 하지만 구현이 복잡하고 특정 항목을 탐색 혹은 추출하려 할 때 시간이 배열로 구현한 순차 리스트 보다 오래 걸린다는 단점이 있다. 연결 리스트의 종류들을 대략적으로 살펴보자.

 

1. 단일 연결 리스트(singly linked list)

단일 연결 리스트

연결 리스트는 우리가 저장하고 싶은 데이터가 들어가는 데이터 필드, 다른 노드를 가리키는 포인터가 저장되는 링크필드가 존재한다. 단일 연결리스트는 링크필드가 다음 노드를 가르키고 마지막 노드의 링크는 NULL 값을 가짐으로써 연결 리스트의 마지막을 표현하는 것이 특징이다.

 

2. 원형 연결 리스트(circular linked list)

원형 연결 리스트

마지막 노드의 링크가 NULL이 아니라 첫 번째 노드를 가리키는 게 특징이다. 따라서 모든 노드로 언제든지 탐색이 가능하다. 원형 연결 리스트는 하나의 노드에서 다른 모든 노드로의 접근이 가능하여 삽입과 삭제가 용이하다는 장점을 갖고 있다.

 

3. 이중 연결 리스트(doubly linked list)

이중 연결 리스트

한 노드에 오른쪽 왼쪽 링크가 존재하여 앞뒤 노드가 서로 연결되어 있다. 왼쪽 링크는 앞에 있는 노드, 오른쪽 링크는 뒤에 있는 노드를 가리키는 구조이다. 이중 연결 리스트는 특정 노드에서 양방향으로 자유롭게 움직일 수 있다. 이는 상당한 장점이다.(단일 연결 리스트는 선행 리스트를 찾기 어려우며, 원형 연결 리스트는 한 바퀴를 다시 돌아야 하는 불편함이 있음) 하지만 공간 차지를 많이 하고 코드가 복잡하다는 단점이 존재한다.

---

리스트에 대한 종류와 대략적인 모습들을 보았다.

 

각 리스트에 대한 자세한 특징과 코드들은 추후 각각의 주제로 포스팅하도록 하겠다.