[ 자료구조 및 알고리즘 ] 5.연결 자료구조 - 2. 단순 연결 리스트

단순 연결 리스트(singly linked list)

: 노드가 하나의 링크 필드에 의해서 다음 노드와 연결되는 구조를 가진 연결 리스트

- 연결 리스트, 선형 연결 리스트(linear linked list), 단순 연결 선형 리스트(singly linked linear list)

 

단순 연결 리스트의 삽입

리스트 week2=(월, 금, 일)에서 원소 “월”과 “금”사이에 새 원소“수” 삽입하기

1. 삽입할 새 노드를 만들 공백노드를 메모리에서 가져와서 포인터변수 new가 가리키게 한다.

2. new의 데이터 필드에 “수”를 저장한다.

3. new의 앞 노드, 즉 “월”노드의 링크 필드 값을 new의 링크 필드에 저장한다.

4.  new의 값(new가 가리키고 있는 새 노드의 주소)을 “월”노드의 링크 필드에 저장한다

 

 

단순 연결 리스트의 삭제

리스트 week2=(월, 수, 금, 일)에서 원소 “수” 삭제하기

1.  삭제할 원소의 앞 노드(선행자)를 찾는다.

2. 삭제할 원소 “수”의 링크 필드 값을 앞 노드의 링크 필드에 저장한다.

 

 

자유 공간 리스트(free space list)

사용하기 전의 메모리나 사용이 끝난 메모리를 관리의 용이성을 위해

노드로 구성하여 연결한 리스트

자유 공간 리스트에서의 노드 할당 알고리즘

 

 

자유 공간 리스트에서의 노드 할당 과정

• 자유공간 리스트 free에서 노드를 할당할 때는 항상 첫 번째 노드 할당 

• 초기 상태

❶ new ← Free;

리스트 free의 첫 번째 노드의 주소(Free)를 포인터 new에 저장하여 포인터 new가 할당할 노드를 가리키게 한다.

 

❷ Free ← Free.link;
• 포인터 free에 리스트의 두 번째 노드의 주소(Free.link)를 저장

• 이제 자유공간 리스트 free의 첫 번째 노드는 리스트에서 의미적으로 분리된 상태이므로 포인터 new를 반환(return new;)해줌으로써
새 노드를 할당

 

자유 공간 리스트로의 노드 반환 알고리즘

 

 

자유 공간 리스트로의 노드 반환 과정

• 반환되는 노드는 자유공간 리스트 free의 첫 번째 노드로 다시 삽입 

• 초기 상태

❶ old.link ← Free;

자유 공간리스트 free의 첫 번째 노드주소(Free)를 반환할 노드 포인터 old.link 에 저장하여 포인터 old의 노드가 리스트 free의 첫 번째 노드를 가리키게 한다.

❷ Free ← old;

포인터 old의 값 즉, 반환할 노드의 주소(old)를 포인터 free에 저장하 여 리스트 free의 첫 번째 노드로 지정

 

 

 

단순 연결 리스트의 삽입 알고리즘 

3가지 경우 고려

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

2 중간 노드로 삽입하는 경우
3 마지막 노드로 삽입하는 경우

 

 

첫 번째 노드로 삽입하기

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

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

new.link ← L;

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

❹L ← new;

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

 

 

 

중간 노드로 삽입하기

• 리스트 L에서 포인터변수 pre가 가리키고 있는 노드의 다음에 데이터 필드 값이 x인 새 노드를 삽입하는 알고리즘

❶<< 리스트 L이 공백 리스트인 경우 >>

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

-b new.link ← null;

리스트의 마지막 노드인 new의 링크 필드에 null을 저장하여 마지막 노드임을 표시

 

❷<< 리스트 L이 공백 리스트가 아닌 경우 >>

 

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

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

 

 

 

마지막 노드로 삽입하기

• 새 노드 new를 마지막 노드로 삽입하는 알고리즘

❶<< 리스트 L이 공백 리스트인 경우 >>
• [알고리즘 5-4]에서 공백리스트에 노드를 삽입하는 연산과 같은 연산 

• 삽입하는 새 노드 new는 리스트 L의 첫 번째 노드이자 마지막 노드

❷<< 리스트 L이 공백 리스트가 아닌 경우 >>

-a temp ← L;

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

-b while (temp.link ≠ null) do temp ← temp.link;

• while 반복문을 수행하여 순회포인터 temp가 노드의 링크 필드를 따라 이동하 면서 링크 필드가 null인 마지막 노드 찾기 수행

-c temp.link ← new;

순회포인터 temp가 가리키는 노드 즉, 리스트의 마지막 노드의 링크 필드(temp.link)에 삽입할 새 노드 new의 주소를 저장하여, 리스트의 마지막 노드가 새 노드 new를 연결

 

 

 

단순 연결 리스트의 삭제 알고리즘

 리스트 L에서 포인터 pre가 가리키는 노드의 다음 노드를 삭제하는 알고리즘
• 포인터old:삭제할노드

❷<< 리스트 L이 공백 리스트가 아닌 경우 >>

-a old ← pre.link;

노드 pre의 다음노드의 주소(pre.link)를 포인터 old에 저장하여, 포인터 old가 다음 노드를 가리키게 한다.

-b if (old = null) then return;
• 만약 노드 pre가 리스트의 마지막 노드였다면 :

포인터 pre가 가리키는 노드가 마지막 노드인 경우에, 2-a old ← pre.link; 를 수행한 상태 :

.3

⇒ pre.link의 값은 null이므로 포인터 old의 값은 null이 된다. 결국 노드 pre 다음에 삭제할 노드가 없다는 의미이므로 삭제연산을 수행하지 못 하고 반환(return).

-c pre.link ← old.link;

삭제할 노드 old의 다음 노드(old.link)를 노드 pre의 다음 노드(pre.link)로 연결

.

-d returnNode(old);
삭제한 노드 old를 자유 공간리스트에 반환

 

 

단순 연결 리스트의 노드 탐색 알고리즘

리스트의 노드를 처음부터 하나씩 순회하면서 노드의 데이터 필드의 값과 x를 비교하여 일치하는 노드를 찾는 연산

 

 

 

단순 연결 리스트의 단점

현재 탐색지점 이전 노드의 검색이 어려움