[Data-Structure] Linked List

Array 자료구조는 논리적 저장 순서와 물리적 저장 순서가 일치하는 순차적 리스트이다. 저장 순서에 따라 할당된 인덱스 값으로 위치하는 element에 접근할 수 있으며, Array의 element 중 하나를 삭제하게되면 해당 원소에 접근하여 작업을 완료한 뒤 (O(1)) 삭제한 원소보다 더 큰 인덱스를 갖는 원소들을 shift하여 해당 원소가 비어있는 빈 공간을 없앤다.(O(n)) Array로 구현한 순차적 리스트의 단점은 연산 시 원소에 접근하여 작업을 완료한 뒤 또 한 가지의 작업을 추가적으로 해줘야 하는 것이다. (삽입 시에도 첫번째 자리에 새로운 원소를 추가한다면, 모든 원소들의 인덱스를 1씩 shift해줘야한다.)

 

순차적 리스트의 단점을 보완하기위한 자료구조가 Linked List이다. Linked List의 각 원소들은 자기 자신 다음에 어떤 원소가 있는지 기억하고 있다. 따라서, 이 부분만 다른 값으로 바꿔주면 삭제와 삽입을 O(1)만에 해결할 수 있다는 것이 장점이다. Linked List의 구조는 기본적으로 헤드와 노드로 구분된다.

 

 

 

 

헤드 : 데이터가 저장되지 않고 'List의 처음 노드를 가르키는 역할'만을 하는 자료구조 (진입점)
노드 : 1) 데이터 필드와 2)링크 필드로 나뉘며, 데이터 필드는 데이터를 저장하고 링크 필드는 다음 순서 노드의 주소값을 저장한다. 

 

 

• Linked List의 종류

1) 단순 연결 리스트

 

Array에서의 삭제 연산 시 데이터가 삭제된 인덱스의 빈 공간이 그대로 남아 메모리의 낭비가 생겼다면, Linked List에서의 삭제 연산은 다음과 같은 프로세스로 삭제를 O(1)만에 해결한다. 

 

a. 삭제할 노드의 선행노드를 탐색한다.

b. 삭제할 노드의 링크 필드를 선행 노드의 링크 필드에 복사한다.

(=> 결과적으로 삭제할 노드를 가르키는 노드가 없어지므로 삭제된 것과 같은 기능을 하게 됨.)

 

 

노드 1개가 데이터 필드와 링크 필드로 구성된 단순 연결 리스트

 

 

 

 

 

2) 이중 연결 리스트

 

단순 연결 리스트는 한번 링크를 따라가기 시작하면 선행 노드로 돌아가는 것이 불가하다. 원하는 노드를 지나쳤다면 헤드부터 다시 링크를 따라가서 이동해야 한다. 이와 같은 단순 연결 리스트의 단점을 보완한 것이 이중 연결 리스트이다. 이중 연결 리스트의 노드는 1개의 데이터 필드와 2개의 링크 필드로 이루어져, 각각 선행 노드의 주소와 후행 노드의 주소를 저장한다.

 

노드 1개가 데이터 필드와 2개의 링크 필드로 구성된 이중 연결 리스트