선형 리스트(Linear List)와 연결 리스트(Linked List)

선형 리스트(linear list)

 데이터가 배열처럼 연속하는 공간에 저장되어 순서를 갖는다.

 

연결 리스트(linked list)

 각각의 데이터 안에 다음 데이터에 대한 정보가 저장되어 있어 서로 연결된다. 리스트에 데이터를 삽입할 때 노드용 객체를 만들고, 삭제할 때 노드용 객체를 없애는 방식으로 구현한다.

 

Linked List의 구조

 

배열

 연속된 메모리 주소값 안에 데이터를 넣는 구조로 위치를 바꾸려면 데이터가 전체적으로 이동해야 한다.

연결 리스트

 흩어져 있는 공간에 노드들의 연결로 이루어져 있다. 각 노드는 다음 노드를 가리키며, 연속된 메모리 주소가 아니기 때문에 직접 주소 값을 가지도 있어야 다음 노드로 접근이 가능하다. 마지막 노드는 새 노드가 추가되기 전까지 null을 가리킨다.

 

연결 리스트의 장점이자 배열의 단점

 연결리스트는 순서가 지정되지 않기 때문에 데이터를 담은 노드를 어느 위치든 쉽게 추가하거나 삭제할 수 있다. 그러나 배열에서는 중간에 데이터를 추가하고 싶은 경우 제일 마지막 인덱스를 새로 만들어 삽입하고자 하는 인덱스까지 모든 데이터를 한 칸씩 이동한 후에 원하는 인덱스에 값을 추가할 수 있다. 삭제의 경우도 마찬가지이다.

 

배열의 장점이자 연결 리스트의 단점

 배열은 연속적으로 이어져 있어 주소의 계산이 쉽기 때문에 특정 노드로 쉽게 접근이 가능하다. 그러나 연결 리스트의 경우 노드가 메모리에 흩어져 있어 특정 노드로 가려면 첫 번째 노드인 head 노드에서 순회하여 마지막 노드인 tail 노드까지 순차적으로 검색하여야 한다.