원형 연결 리스트
단순 연결 리스트에서 마지막 노드가 리스트의 첫 번째 노드를 가리키게 해서 리스트의 구조를 원형으로 만든 리스트
<첫번째 노드에 삽입하는 알고리즘>
1. 첫번째 노드의 주소를 temp에 저장해서 순회 시작점을 지정한다. (temp는 순회용 포인터임.)
2. while문 돌려서 temp를 마지막 노드까지 이동시킨다.
3. 노드 new가 temp의 다음 노드, 즉 삽입하기 전 리스트의 첫번째 노드를 가리키게 함. 원형 연결 리스트이기 때문에 마지막 노드의 다음 노드가 첫번째 노드가 된다.
4. 포인터 new의 값을 포인터 temp가 가리키고 있는 마지막 노드의 링크에 저장하여 마지막 노드가 노드 new를 가리키게 한다.
5. 노드 new의 주소를 리스트 포인터에 저장한다. 이 과정으로 노드 new가 리스트의 첫번째 노드로 지정된다.
<중간에 삽입하는 알고리즘>
포인터 pre가 가리키는 노드의 다음 노드로 삽입하기. 원형이 아닌 단순 연결리스트에서의 삽입과 똑같음. 노드 new의 주소를 노드 pre에 저장하고 노드 pre가 노드 new를 가리키게 한다. 가장 마지막 노드가 맨 앞에 연결되면 원형 연결 리스트인데 중간에 노드를 삽입해도 끝 부분에는 영향이 없음.
1. new.link = pre.link
2. pre.link = new
public void insertFirstNode(CircularList CL, ListNode pre, String x) {
ListNode newNode = new ListNode(x);
if (CL.head == null) {
CL.head = newNode;
newNode.link = newNode;
}
else {
newNode.link = pre.link;
pre.link = newNode;
}
}
'Major > Data Structure & Algorithm' 카테고리의 다른 글
Stack , 괄호검사(Valid Braces), Infix to Postfix algorithm (0) | 2022.04.16 |
---|---|
review (0) | 2022.04.16 |
이중 연결 리스트의 삽입, 삭제 + (다항식 연산 ) (0) | 2022.04.13 |
연결리스트 노드 개수 카운팅,특정 노드 순서 바꾸기,첫번째 노드 삭제하기 ... (0) | 2022.04.03 |
[JAVA] 연결리스트, 노드, 삽입 및 삭제 (0) | 2022.04.03 |