[자료구조] Linked List - 삽입, 삭제 개념

리스트는 자료를 구조화하는 가장 기본적인 방법으로서, 값들을 나열한다. 리스트에서는 새로운 항목을 리스트의 처음, 중간,끝에 삽입하여 저장할 수 있다. 그리고 리스트의 특정 부분을 추출하거나 특정 값을 삽입 혹은 삭제할 수 있다.

 

리스트는 구현이 간단하지만 삽입 삭제시 오버헤드가 발생할 가능성이 있는 Linear List와, 삽입 삭제가 효율적이지만 구현이 복잡한 Linked List로 나뉜다.

 

Linked List에서 한 원소가 삽입되면, 그 이후의 원소들은 한 자리씩 자리를 뒤로 이동하여 물리적 순서를 논리적 순서와 일치시켜야만 한다. 삽입을 위해서는 먼저 원소를 삽입할 빈 자리를 만들어서, 빈 자리에 원소를 삽입한다. (빈 자리를 만들기 위해 기존의 원소들은 한칸씩 뒤로 이동시킨다)

 

즉 n+1개의 원소로 이루어진 리스트에서 k번째 자리에 원소를 삽입할 경우 n-k+1개의 원소를 이동시켜야 한다. 따라서 이동 회수는 n-k+1가 된다.(마지막 원소의 인덱스 - 삽입할 자리의 인덱스 + 1)

 

Linked List에서 한 원소가 삭제되면, 그 이후의 원소들은 한 자리씩 앞으로 자리를 이동하여 물리적 순서를 논리적 순서와 일치시켜야만 한다. 삭제를 위해서 원소를 먼저 삭제하고, 삭제한 빈 자리를 뒤에 위치한 원소들이 채워지도록 한다.

 

즉 n+1개의 원소로 이루어진 리스트에서 k번째 자리에 있는 원소를 삭제할 경우, k+1번째 원소부터 n번째 원소까지 n-k개의 원소를 이동시킨다. 이동횟수는, n-(k+1) + 1 = n-k가 된다.