일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 | 31 |
- 자료구조
- 컴퓨터구조
- 딥러닝 교차 엔트로피
- 오퍼랜드
- 리스트
- 확률분포
- 뇌를 자극하는 알고리즘
- 단층퍼셉트론
- 인공지능
- 엔트로피
- 파이썬 날코딩으로 알고 짜는 딥러닝
- 파이썬 딥러닝
- 연결 자료구조
- 회귀분석
- 신경망
- 선형 리스트
- 단층 퍼셉트론
- 순차 자료구조
- 딥러닝
- 퍼셉트론
- 자연어처리
- DBMS
- 딥러닝 교차엔트로피
- 파라미터
- 자료구조 알고리즘
- DB
- 노드
- 편미분
- lost function
- 교차 엔트로피
- Today
- Total
YZ ZONE
[ 자료구조 및 알고리즘 ] 5.연결 자료구조 - 3. 원형 연결 리스트 본문
원형 연결 리스트(circular linked list)
단순 연결 리스트에서 마지막 노드가 리스트의 첫 번째 노드를 가리키게 하여 리스트의 구조를 원형으로 만든 연결 리스트
• 단순 연결 리스트의 마지막 노드의 링크 필드에 첫 번째 노드의 주소를 저장하여 구성
• 링크를 따라 계속 순회하면 이전 노드에 접근 가능
• 선형 기차놀이와 원형 기차놀이 비교
![](https://blog.kakaocdn.net/dn/bkmZps/btr1lvy1mNc/8Ee7nNYyuzLEEml8MG2g3k/img.jpg)
원형 연결 리스트의 삽입 연산
마지막 노드의 링크를 첫 번째 노드로 연결하는 부분만 제외하고는 단순 연결 리스트에서의 삽입 연산과 같은 연산
3가지 경우
• 첫 번째 노드로 삽입하는 경우
• 중간 노드로 삽입하는 경우
• 마지막 노드로 삽입하는 경우
− 중간 노드로 삽입하는 경우의 알고리즘 사용 가능
- 첫 번째 노드로 삽입하기
• 원형 연결 리스트 CL에 x 값을 갖는 노드 new를 삽입하는 알고리즘
![](https://blog.kakaocdn.net/dn/bHK0gl/btr1HgNPubb/8s2npJ8kwn9fckCjKV9Z20/img.png)
❶<< 원형리스트가 공백 리스트인 경우 >>
• 삽입하는 노드new는 리스트의 첫 번째 노드이자 마지막 노드가 되어야 함
![](https://blog.kakaocdn.net/dn/dlSx42/btr1lz9sE1e/Kd62Ba0nnkZphv0Zc5KI80/img.jpg)
1. CL ← new;
• 포인터 CL이 노드 new를 가리키게 한다.
![](https://blog.kakaocdn.net/dn/cs0R9B/btr1ILmuOO7/koW73MN5oYnCyTflBB3NjK/img.png)
2. new.link ← new;
• 노드 new가 자기자신을 가리키게 함으로써 노드 new를 첫 번째 노드이자 마지막 노드가 되도록 지정한다.
❷<< 원형리스트가 공백 리스트가 아닌 경우 >>
1. temp ← CL;
• 리스트가 공백리스트가 아닌 경우에는 첫 번째 노드의 주소를 임시 순회 포인터 temp에 저장하여 노드 순회의 시작점을 지정한다.
![](https://blog.kakaocdn.net/dn/yLyL2/btr1zl28Y24/4gKwkQ5Z3uPJ9Gqk7fhDNK/img.png)
2. while (temp.link ≠ CL) do temp ← temp.link;
• while 반복문을 수행하여 순회 포인터 temp를 링크를 따라 마지막 노드까지 이동
3. new.link ← temp.link;
4. temp.link ← new;
• 포인터 new의 값을 포인터 temp가 가리키고 있는 마지막 노드의 링크에 저장 하여, 리스트의 마지막 노드가 노드 new를 가리키게 한다.
5. CL ← new;
• 노드 new의 값을 리스트 포인터CL에 저장하여 노드 new가 리스트의 첫 번째 노드가 되도록 지정
알고리즘 5-8 실행 결과
![](https://blog.kakaocdn.net/dn/CHVJb/btr1nwEpC5g/HaLdnBEBWbwKyihdWGzsZK/img.jpg)
- 중간 노드로 삽입하기
• 원형 연결 리스트 CL에 x 값을 갖는 노드 new를 포인터 pre가 가리키는 노드의 다음 노드로 삽입하는 알고리즘
![](https://blog.kakaocdn.net/dn/Jv67Z/btr1Ir9sV0D/PCskurLp1kPYMqJZ2RIB7K/img.png)
❶<< 원형 연결 리스트 CL이 공백 리스트인 경우 >>
• [알고리즘 5-8]에서 공백 리스트에 첫번째 노드를 삽입하는 연산과 같음
❷<< 원형 연결 리스트 CL이 공백 리스트가 아닌 경우 >>
![](https://blog.kakaocdn.net/dn/nyJPQ/btr1I8V7GFg/Pzh2fLtLfqRjFgKp7hcak0/img.jpg)
1. new.link ← pre.link;
노드 pre의 다음 노드로 new를 삽입하기 위해서, 먼저 노드 pre의 다음 노드(pre.link)를 new의 다음 노드(new.link)로 연결
![](https://blog.kakaocdn.net/dn/VLU5g/btr1CLHnSci/XydITAjgKRAD6esey4VdKK/img.png)
2. pre.link ← new;
노드 new의 값(삽입할 노드의 주소)을 노드 pre의 링크에 저장하여, 노드 pre가 노드 new를 가리키도록 한다.
![](https://blog.kakaocdn.net/dn/ciq5rm/btr1lxcw4Hi/gBeEDc1WJUOwZ9RN2inMck/img.png)
원형 연결 리스트의 삭제 연산
원형 연결 리스트 CL에서 포인터 pre가 가리키는 노드의 다음 노드를 삭제하고 삭제한 노드는 자유공간 리스트에 반환하는 연산
• 포인터 old는 삭제할 노드 지시
![](https://blog.kakaocdn.net/dn/J1zGl/btr1ILz2OPQ/9in9nWfXcy8qUxXAJ7xqR1/img.png)
❶ old ← pre.link;
![](https://blog.kakaocdn.net/dn/PAl4z/btr1HheVudR/QvZeC2oXrPmzwRDLte3XI1/img.png)
❷ pre.link ← old.link;
• old의 다음노드(old.link)를 노드 old의 이전노드 pre 노드와 서로 연결
❸<<삭제할노드old가원형연결리스트의첫번째노드인경우 >>
![](https://blog.kakaocdn.net/dn/xDFEO/btr1uc6C576/frSpAjsA85VKRkaoq7NuZ1/img.png)
1. CL ← old.link;
• 첫 번째 노드를 삭제하는 경우에는 노드 old의 링크 값을 리스트 포인터 CL에 저장하여 두 번째 노드가 리스트의 첫 번째 노드가 되도록 조정
원형 연결 리스트의 단점
현재 지점의 이전 노드를 검색하기 위한 비용이 크다
![](https://blog.kakaocdn.net/dn/p2BZ6/btr1yA0s57g/fo2EDVtPOHnACLP8cb0Wk1/img.png)
'IT > 자료구조 및 알고리즘' 카테고리의 다른 글
[ 자료구조 및 알고리즘 ] 5.연결 자료구조 -5. 다항식의 연결 자료 구조 표현 (1) | 2023.03.02 |
---|---|
[ 자료구조 및 알고리즘 ] 5.연결 자료구조 -4. 이중 연결 리스트 (1) | 2023.03.02 |
[ 자료구조 및 알고리즘 ] 5.연결 자료구조 - 2. 단순 연결 리스트 (0) | 2023.02.24 |
[ 자료구조 및 알고리즘 ] 5.연결 자료구조 - 1.연결 자료구조 (0) | 2023.02.24 |
[ 자료구조 및 알고리즘 ] 4. 순차 자료구조 - 4. 행렬의 순차 자료구조 표현 (1) | 2023.02.23 |