[CS] 자료구조 - List

리스트는 어떠한 순서를 가지고 원소들이 나열된 형태의 자료구조이다. 리스트는 순차 리스트와 연결 리스트 두 종류로 구분된다. 보통 순차 리스트는 배열(Array)을 사용해 표현하지만 자바에서는 ArrayList라는 Java API가 따로 존재한다.

 

순차 리스트는 데이터를 삽입하거나 삭제하고 나면, 연속적인 물리적 위치를 유지하기 위해 원소를 옮기는 추가 작업을 해야 하므로 삽입이나 삭제 연산이 많다면 그만큼 시간이 오래 걸린다. (대신 조회 시에는 해당 인덱스만 조회하면 되므로 시간이 단축된다.)

 

연결리스트는 특정 노드를 삽입하거나 삭제할 때 순차 리스트에 비해 연산 속도가 빠르며, 조회 시에는 index[0] 부터 시작되어 연산 속도가 느리다.

 

연결리스트 (LinkedList)

 

Linked List는 순차 리스트와 달리 물리적 위치와 논리적 위치가 다를 수 있으며, 각 원소는 자신 다음 원소의 물리적 위치를 가지고 있다.

 

🌟 Node(노드) : 데이터 저장 단위 (데이터값, 포인터)로 구성되어 있다.

🌟 Pointer(포인터) : 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간.

 

장점

• 미리 데이터 공간을 할당하지 않아도 된다. (순차 리스트 - 배열은 미리 데이터 공간을 할당해야 한다.)

단점

• 연결 정보를 찾는 시간이 필요하므로 접근 속도가 느리다.
• 중간 데이터를 삭제하거나 새로 추가할 경우 앞뒤 데이터의 연결을 재구성해야 하는 부가적인 작업이 필요하다.

Linked List의 종류

 

1. 단일 연결리스트 : 각 노드 당 한 개의 포인터가 있고 포인터는 다음 노드의 위치를 가리킨다. (테일은 가장 마지막이므로 포인터를 가지고 있지 않다.)
2. 이중 연결리스트 : 포인터를 두 개 가지고 있어 이전 노드와 다음 노드를 가리킨다.
3. 원형 연결리스트 : 단일 연결리스트와 같으며 다만 테일에 포인터가 추가된 형태로 테일의 포인터는 헤더를 가리켜 원형이 되도록 한다.

ArrayList

 

자바의 ArrayList는 List 인터페이스를 상속받은 클래스이며, 배열을 이용해 리스트를 구현했다. 배열은 처음에 할당된 만큼의 공간을 사용할 수 있는 반면, ArrayList는 계속해서 데이터를 추가할 수 있고 그에 따라 크기가 가변적으로 변한다.

 

장점

• 배열을 이용하기 때문에 인덱스를 이용할 수 있으며, 그 덕에 조회연산이 빠르다.

단점

• 데이터의 추가/삭제 연산이 느리다. -> 중간에 데이터를 삭제하거나 추가하면 한 칸씩 당기거나 미뤄야 함 (shift)

 

💡 공부 중 정리하는 내용이므로 부족한 부분이 있을 수 있습니다.