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

리스트 (List)

  리스트는 가장 대표적인 자료구조 중 하나로 Array, List, Stack, Queue 등과 함께 데이터에 순서가 존재하는 선형 자료구조(Linear Data Structure)에 속한다. (참고로 비선형 자료구조에는 Tree, Graph, Set 등이 존재한다.)

출처 : https://www.interviewbit.com/data-structure-interview-questions/

 

리스트의 구현 방법

  리스트를 구현하는 방법에는 크게 두 가지 방법이 존재한다. 논리적으로만 데이터를 연속하게 저장하는 방법이 있고 두 번째는 물리적으로도 데이터를 연속하게 저장하는 방법이다. 

 

1. ArrayList

  ArrayList는 데이터를 논리적 순서에 따라 물리적 메모리에 연속해서 저장한다. 메모리 중간에 빈 공간이 존재하면 안되기 때문에 데이터를 중간에 삽입하거나 삭제할 경우 데이터 위치를 재조정하는 작업이 필요하다.

 

 

2. Linked List

  Linked List(연결 리스트)에서 데이터는 실제 메모리상으로 연속된 공간에 존재하지 않는다. Linked List에서 각각의 데이터는 노드에 저장되며 링크를 통해 서로 연결되고 그 순서가 유지된다. Linked List는 노드 간 링크를 유지하는 방법에 따라 다시 세 가지로 분류될 수 있다.

(1) Single Linked List

  단방향 연결 리스트이다. 각각의 노드는 다음 노드의 링크를 가지고 있다. 하지만 이전 노드는 알 수 없다.

 

(2) Double Linked List

  양방향 연결 리스트이다. 각각의 노드는 이전 노드와 다음 노드에 대한 정보를 모두 가지고 있다.

 

(3) Circular Linked List

  전체 구조가 원형을 띄는 연결 리스트이다. 마지막 노드(Tail)의 다음 노드가 null인 다른 연결 리스트와 다르게 마지막 노드가 첫 번째 노드(Tail)와 연결된다.

 

 

※ ArrayList vs Linked List

  ArrayList와 Linked List는 그 장점과 단점이 뚜렷한 리스트 구현 방법들이다.

  먼저 ArrayList의 경우 물리적인 순서를 유지하기 때문에 인덱싱을 활용할 수 있다. 그렇기 때문에 데이터를 조회할 때 큰 강점을 지닌다. 하지만 물리적 순서를 유지하기 위해 데이터를 삽입하거나 삭제할 때 데이터 위치를 재조정하는 비용이 발생한다.

  한편 Linked List는 특정 데이터를 조회하기 위해 첫 노드(Head)부터 원하는 데이터가 나올 때까지 차례대로 링크를 따라가보는 방법밖에 없다. 그렇지만 데이터를 추가하거나 삽입할 때 인근 노드들의 링크만을 수정하면 된다는 점에서 삽입·삭제 연산에서 뛰어난 성능을 보인다.

  즉, ArrayList는 탐색에 Linked List는 삽입·삭제에 강점을 보인다.

 

 

※ Array vs ArrayList (Java를 하는 사람들을 위해)

  Array와 ArrayList 모두 데이터를 물리적인 방식으로 순서대로 저장하고 인덱싱을 제공한다. 메모리에 빈 공간에 존재하면 안 되기 때문에 삽입하거나 삭제를 하면 원소 위치를 일일히 조정해줘야 하는 것도 똑같다. 그렇다면 둘의 차이는 무엇일까? 생각보다 답은 단순하다. Java에서 Array는 고정된 크기를 가진다. 한 번 생성된 Array는 그 크기를 계속 가지고 가야한다. 그러나 배열에 얼만큼의 데이터를 넣을지 예측하는 것은 현실적으로 불가능하며 그렇다고 크기를 크게 만들자니 메모리 낭비가 너무 아깝다. 하지만 ArrayList는 가변적 크기를 가진다. 그렇기 때문에 ArrayList class를 활용하는 것을 추천한다.