커서를 이용한 연결 리스트

이번 단원을 공부하며 내가 저번 단원을 잘못 이해했다는 것을 알았다. 포인터를 이용한 연결 리스트에서 포인터가 지금의 커서라고 생각했었는데 둘의 차이점을 잘 모르겠다.

 

저번 단원에서 원하는 위치에 데이터를 추가하려면 어떻게 해야할까 라는 생각을 하며 원하는 위치 앞, 뒤 위치의 노드 사이에 포인터 주소를 새로운 노드로 다르게 주면 되지 않을까 라는 결론을 내렸었다.

 

하지만 이번 단원에서 같은 내용이 나와버려서 내가 잘못 생각한 건가 라는 생각이 들어 검색을 해봤는데 결국 내가 내린 결론은 포인터와 커서는 비슷한 개념의 용어인것 같다. 

 

일단 그렇게 이해하는게 지금 내가 공부하는데 혼란이 없을 것 같지만 나중에라도 확실히 짚고 넘어가야겠다.

+ 8.9 수정) 책의 앞부분에 나와있었는데 잊어버린것 같다. 책을 조금 더 주의깊게 읽어야지 ㅋ

---

커서

: int 형 정숫값인 인덱스로 나타낸 포인터

 

- 데이터 개수가 크게 변하지 않거나 데이터 최대 개수를 예측할 수 있는 경우에는 커서를 이용한 리스트를 구현하는게 효율적이다.

 

다음은 커서를 이용한 연결리스트의 코드이다.

from __future__ import  annotations
from typing import Any, Type

Null = -1

class Node:     # 노드 클래스

    def __init__(self, data = Null, next = Null, dnext = Null):
        self.data = data
        self.next = next
        self.dnext = dnext

class ArrayLinkedList:  # 연결리스트 커서버전
    def __init__(self, capacity: int):
        self.head = Null
        self.current = Null
        self.max = Null			# 배열에서 맨 끝 쪽에 저장되는 노드의 레코드 번호
        self.deleted = Null		# 프리리스트의 머리 노드를 참조하는 커서
        self.capacity = capacity          # 리스트의 크기
        self.n = [Node()] * self.capacity   # 리스트 본체
        self.no = 0

    def __len__(self):
        return self.no

    def get_insert_index(self):
        '''다음에 삽입할 데이터의 인덱스를 구핢'''
        if self.deleted == Null:
            if self.max + 1 < self.capacity:
                self.max += 1
                return self.max
            else:
                return Null
        else:
            rec = self.deleted
            self.deleted = self.n[rec].dnext
            return rec

    def delete_index(self, idx):
        '''레코드 idx를 프리 리스트에 등록'''
        if self.deleted == Null:
            self.deleted = idx
            self.n[idx].dnext = Null

        else :
            rec = self.deleted
            self.deleted = idx
            self.n[idx].dnext = rec


    def search(self,data):
        '''data와 같은 노드 검색'''
        cnt = 0                     # 현재 스캔중인 노드
        ptr = self.head             # 포인터
        while ptr != Null:
            if self.n[ptr].data == data:
                self.current = ptr
                return cnt
            cnt += 1
            ptr = self.n[ptr].next
        return Null

추가, 삭제와 같은 다른 기능들은 이전에 포인터를 이용하는 연결리스트와 다른 점이 없어 넣지않았지만 결국 앞의 내용을 이해하는 것이 중요한 것 같다.

 

배열 안에 원소를 추가할 때 주의할 점은 삽입 노드의 저장장소는 배열 안에서 가장 끝 쪽에 있는 인덱스의 위치이지 연결리스트의 끝이 아니다.

 

프리리스트

 

삭제된 레코드 그룹을 관리할 때 사용하는 자료구조. 프리리스트를 이용하여 삭제 후 비어있는 배열의 문제를 해결할 수 있음