1. 단순 연결 리스트의 삽입 방법과 알고리즘
가. 단순 연결 리스트에서의 삽입 예시
나. 단순 연결 리스트에 삽입하는 방법
1) 초기 상태
단순 연결 리스트 week2에 노드를 삽입하기 전인 초기 상태
2) 삽입할 노드를 준비함
공백 노드를 가져와 포인터 변수 new가 가리키게 함.
3) 새 노드의 데이터 필드에 값을 저장함
new의 데이터 필드에 "수"를 저장
4) 새 노드의 링크값을 지정함
new의 앞 노드, 즉 "월" 노드의 링크 필드 값을 new의 링크 필드에 저장
5) 리스트의 앞 노드에 새 노드를 연결함
new의 값을 "월" 노드의 링크 필드에 저장
다. 단순 연결 리스트의 첫 번째 노드로 삽입 알고리즘
1) new ← getNode()
삽입할 노드에 대한 메모리를 할당 받아서(getNode()), 포인터 new에 설정
2) new.data ← x
새 노드의 데이터 필드에 x를 저장
3) new.link ← L
삽입할 노드를 연결하기 위해서 리스트의 첫 번째 노드 주소(L)을 삽입할 새 노드 new의 링크 필드(new.link)에 저장하여, 새노드 new가 리스트의 첫 번째 노드를 가리키게 함.
4) L ← new
리스트의 첫 번째 노드 주소를 저장하고 있는 포인터 L에 새 노드의 주소 new를 저장하여, 포인터 L이 새 노드를 첫 번째 노드로 가리키도록 지정.
라. 단순 연결 리스트의 중간 노드로 삽입 알고리즘
1) new ← getNode()
삽입할 노드에 대한 메모리를 할당 받아서 (getNode()), 포인터 new에 설정
2) new.data ← x
새 노드의 데이터 필드에 X를 저장
3-1) (빈 리스트인 경우) L ← new
리스트 포인터 L에 새 노드 new의 주소를 저장하여, 새 노드 new가 리스트의 첫 번째 노드가 되도록 함.
3-2) (빈 리스트인 경우) new.link ← NULL
리스트의 마지막 노드인 new의 링크 필드에 NULL을 저장해 마지막 노드임을 표시
4-1) new.link ← pre.link
노드 pre의 링크 필드 값을 노드 new의 링크 필드에 저장하여, 새 노드 new가 노드 pre의 다음 노드를 가리키도록 함.
4-2) pre.link ← new
포인터 new의 값을 노드 pre의 링크 필드에 저장하여, 노드 pre가 새 노드 new를 다음 노드로 가리키도록 함.
마. 단순 연결 리스트의 마지막 노드로 삽입 알고리즘
1) new ← getNode()
2) new.data ← x
3) new.link ← NULL
4) (빈 배열일 경우) L ← new
리스트 포인터 L에 새 노드 new의 주소를 저장하고, new는 리스트 L의 첫 번째 노드이자 마지막 노드가 됨.
5-1) temp ← L
현재 리스트 L의 마지막 노드를 찾기 위해서 노드를 순회할 임시 포인터 temp에 리스드의 첫 번째 노드의 주소(L)를 지정
5-2) temp ← temp.link
순회 포인터 temp가 가리키는 노드의 링크 필드가 NULL이 아닌 동안(while temp.link != NULL) 링크 필드를 따라 순회
5-3) temp.link ← new
마지막 노드의 링크 필드에 새 노드 new 주소 저장
2. 단순 연결 리스트의 삭제 방법과 알고리즘
가. 단순 연결 리스트에서의 삭제 예시
나. 단순 연결 리스트에서 노드를 삭제하는 방법
1) 초기 상태
2) 앞 노드를 찾음
삭제할 원소의 앞 노드(선행자)를 찾음.
3) 앞 노드에 링크 필드 값 수정
삭제할 원소의 링크 필드 값을 앞 노드의 링크 필드에 저장
4) 삭제한 노드의 앞뒤 노드가 연결되며 종료
다. 단순 연결 리스트 삭제 알고리즘
1) 공백 리스트인 경우
삭제할 노드가 없으므로 오류 처리
2) old ← pre.link
노드 pre의 다음 노드의 주소(pre.link)를 포인터 old에 저장하여, 포인터 old가 다음 노드를 가리키게 함.
3) if (old = NULL) then return
노드 pre가 마지막 노드였다면 삭제할 노드가 없으므로 바로 종료
4) pre.link ← old.link
5) returnNode(old)
삭제한 노드 old의 메모리를 반환
3. 단순 연결 리스트의 노드 탐색 알고리즘
가. 노드를 탐색하는 알고리즘과 프로그램
연결리스트에서 원소값이 x 인 노드를 탐색하려면 리스트의 노드를 처음 부터 하나씩 순회하면서 현재 노드의 데이터 필드값과 x값과 비교하여 일치하는 노드를 찾아야 함.
1) temp ← L
리스트 L의 시작주소를 노드를 탐색할 때 사용할 순회 포인터 temp에 저장하여 포인터 temp의 시작위치를 지정함.
2) if (temp.data = x) then return temp
현재 temp 노드의 데이터 필드 값이 탐색 값 x와 같으면 현재 temp값을 return하여 x가 있는 노드 주소를 알려줌.(탐색 성공)
3) else temp ← temp.link
현재 필드 값과 탐색 값 x이 같지 않으면 탐색을 계속 해야하므로 링크를 따라 다음 노드로 이동.
4) return temp
마지막까지 탐색해도 x를 찾지 못하면 마지막 노드의 링크 필드 값인 NULL 반환(탐색 실패)
나. 단순 연결 리스트에서 역순으로 변경하는 알고리즘
1) 시작 상태
포인터 p를 첫 번째 노드에 설정, q, r은 NULL
2) q ← p
포인터 q를 포인터 p가 가리키는 현재 노드에 연결
3) p ← q.link, q.link ← r
4) r ← q
5) p 가 NULL이 될 때까지 반복
6) L ← q
