단순 연결 리스트의 삽입

<단순 연결 리스트의 삽입>

 삽입의 알고리즘은 첫 번째 노드로 삽입하는 경우, 중간 노드로 삽입하는 경우, 마지막 노드로 삽입하는 경우로 나뉜다.

 

1. 첫 번째 노드로 삽입하는 경우

① new ← getNode();
삽입할 노드를 자유 공간리스트에서 할당받는다.

② new.data ← x;
새 노드의 데이터 필드에 x를 저장

③ new.link ← L;
삽입할 노드를 연결하기 위해서 리스트의 첫 번째 노드 주소(L)를 삽입할 새 노드 new의 링크 필드(new.link)에 저장하여, 새 노드 new가 리스트의 첫 번째 노드를 가리키게 한다.

④ L ← new;
리스트의 첫 번째 노드 주소를 저장하고 있는 포인터 L에, 새 노드의 주소 new를 저장하여, 포인터 L이 새 노드를 첫 번째 노드로 가리키도록 지정

2. 중간 노드로 삽입하는 경우

중간에 노드를 삽입하기 위해서는 삽입할 위치의 앞에 있는 선행자 노드를 알려주는 포인터 pre가 필요하다. 공백 리스트일 경우와 공백 리스트가 아닐 경우로 나뉜다.

3. 마지막 노드로 삽입하는 경우

마지막에 노드를 삽입하기 위해서는 먼저 마지막 노드를 찾아야 한다. 링크 필드가 null인 노드가 마지막 노드이다. 마지막 노드를 찾기 위해서는 리스트의 노드들을 순회하는 임시 포인터 temp가 필요하다. 공백 리스트일 경우와 공백 리스트가 아닐 경우로 나뉜다.

[공백 리스트일 경우]

① L ← new;
리스트 포인터 L에 새 노드 new의 주소를 저장하여, 새 노드 new가 리스트의 첫 번째 노드가 되도록 한다.

② new.link ← null;
리스트의 마지막 노드인 new의 링크 필드에 null을 저장하여 마지막 노드임을 표시한다.

[공백 리스트가 아닐 경우]

① new.link ← pre.link;
노드 pre의 링크 필드 값을 노드 new의 링크 필드에 저장하여, 새 노드 new가 노드 pre의 다음 노드를 가리키도록 한다.

② pre.link ← new;
포인터 new의 값을 노드 pre의 링크 필드에 저장하여, 노드 pre가 새 노드 new를 다음 노드로 가리키도록 한다.

3. 마지막 노드로 삽입하는 경우

마지막에 노드를 삽입하기 위해서는 먼저 마지막 노드를 찾아야 한다. 링크 필드가 null인 노드가 마지막 노드이다. 마지막 노드를 찾기 위해서는 리스트의 노드들을 순회하는 임시 포인터 temp가 필요하다. 공백 리스트일 경우와 공백 리스트가 아닐 경우로 나뉜다.

[공백 리스트일 경우]

① L ← new;

​리스트 포인터 L에 새 노드 new의 주소를 저장하여, 새 노드 new가 리스트의 첫 번째 노드가 되도록 한다.

② temp ← L;
현재 리스트 L의 마지막 노드를 찾기 위해서 노드를 순회할 임시포인터 temp에 리스트의 첫 번째 노드의 주소(L)를 지정​