#2 양방향 연결 리스트(Doubly Linked List) 구현

1. ADT 작성 

Datas:
    head : 첫 노드를 가리키는 포인터
    tail : 마지막 노드를 가리키는 포인터
    it : 이터레이션을 위한 포인터
    size : 리스트의 크기 = 리스트에 들어있는 노드의 갯수
    
Operations:
    insert(e, i) : 데이터 e를 리스트의 i번째 위치에 삽입. i == -1이라면 마지막에 삽입
    delete_at(i) : i 번째 데이터를 삭제하고 삭제한 데이터를 반환
    delete(e) : 데이터 e를 찾아 삭제하고 결과를 반환
    search_at(i) : i 번째 데이터를 반환. 유효하지 않은 인덱스라면 에러 발생
    search(e) : 데이터 e가 처음으로 나타나는 인덱스를 찾아 반환

 

2. 구현

# 양방향 연결리스트 클래스
class DoublyLinkedList:
    # 노드 클래스
    class __Node:
        # 노드 생성자
        def __init__(self, e):
            # 데이터
            self.data = e

            # 다음 노드
            self.next = None

            # 이전 노드
            self.prev = None

    # 리스트 생성자
    def __init__(self):
        # head
        self.__head = None

        # tail
        self.__tail = None

        # 현재 노드 (iterator 구현을 위한 필드)
        self.__it = self.__Node(0)

        # 리스트 크기
        self.__size = 0

    # 삽입 메소드
    def insert(self, e, i=-1):
        # 삽입할 노드 생성
        new_node = self.__Node(e)

        # 인덱스가 생략됐거나 마지막 인덱스인 경우 맨 끝에 삽입
        if i < 0 or i == self.__size:
            # 리스트가 비어있다면 head = tail = new_node
            if not self.__head:
                self.__head = self.__tail = new_node

            # 리스트가 비어있지 않다면 마지막 노드 뒤에 삽입
            else:
                self.__tail.next = new_node
                new_node.prev = self.__tail
                self.__tail = new_node

        # 마지막 노드가 아닌 인덱스가 주어졌을 경우
        else:
            # 유효하지 않은 인덱스라면 IndexError 발생
            if i > self.__size:
                raise IndexError

            # 인덱스가 0이라면 첫 노드의 앞 부분에 삽입
            if i == 0:
                self.__head.prev = new_node
                new_node.next = self.__head
                self.__head = new_node

            # 그렇지 않다면 해당 인덱스의 노드 앞 부분에 삽입
            else:
                cur = self.__head
                for _ in range(i):
                    cur = cur.next
                cur.prev.next = new_node
                new_node.prev = cur.prev
                cur.prev = new_node
                new_node.next = cur

        # 리스트의 크기 1 증가
        self.__size += 1

    # 탐색 메소드 - 인덱스
    def search_at(self, i):
        # 유효하지 않은 인덱스라면 IndexError 발생
        if i < 0 or i >= self.__size:
            raise IndexError

        # head 부터 i만큼 다음 노드로 이동
        cur = self.__head
        for _ in range(i):
            cur = cur.next

        # 노드의 데이터 반환
        return cur.data

    # 탐색 메소드 - 데이터
    def search(self, e):
        cur = self.__head
        idx = 0
        # 데이터 값이 e인 노드가 나올 때 까지 탐색
        while cur and cur.data != e:
            cur = cur.next
            idx += 1

        # 데이터 값이 e인 노드가 없을 경우 ValueError 발생
        if not cur:
            raise ValueError

        # 데이터 값이 e인 노드가 처음으로 나타난 인덱스 반환
        return idx

    # i 번째 노드 삭제 메소드
    def delete_at(self, i):
        # 유효하지 않은 인덱스라면 IndexError 발생
        if i < 0 or i >= self.__size:
            raise IndexError

        # head 부터 i 만큼 다음 노드로 이동
        cur = self.__head
        for _ in range(i):
            cur = cur.next

        # 반환할 노드의 데이터를 저장
        res = cur.data

        # 앞, 뒤 노드가 서로 연결되도록 조정
        # head, tail 을 삭제한 경우 head, tail 재지정
        if cur.prev:
            cur.prev.next = cur.next
        else:
            self.__head = cur.next

        if cur.next:
            cur.next.prev = cur.prev
        else:
            self.__tail = cur.prev

        # 리스트 크기 1 감소
        self.__size -= 1

        # 삭제한 데이터 반환
        return res

    # 처음으로 나타나는 데이터 e 삭제 메소드
    def delete(self, e):
        # 데이터 삭제 시도
        try:
            # search 메소드를 호출하여 데이터의 인덱스를 구함
            idx = self.search(e)

            # delete_at 메소드를 호출하여 데이터 삭제
            self.delete_at(idx)

            # 삭제성공. True 반환
            return True

        # 존재하지 않는 데이터라면 삭제에 실패. False 반환
        except ValueError:
            return False

    # len 함수의 결과로 sef.__size 반환
    def __len__(self):
        return self.__size

    # 이터레이터 구현
    def __iter__(self):
        # 이터레이션을 위한 self.__it 객체의 next 를 self.__head 로 하고 self 를 반환
        self.__it.next = self.__head
        return self

    def __next__(self):
        # 다음 노드가 있다면 self.__it = self.__it.next 후 self.__it 의 데이터값 반환
        if self.__it.next:
            self.__it = self.__it.next
            return self.__it.data
        # 없다면 이터레이션 종료
        else:
            raise StopIteration


# 테스트
def main():
    # 연결 리스트 생성
    dlist = DoublyLinkedList()
    
    # 데이터 삽입
    dlist.insert(3)
    dlist.insert(1)
    dlist.insert(2)
    dlist.insert(4)
    dlist.insert(0)
    dlist.insert(6)
    dlist.insert(7)
    dlist.insert(9)

    # 데이터 4 삭제
    dlist.delete(4)

    # 첫 번째 데이터(3) 삭제
    dlist.delete_at(0)

    # 3 번째 데이터(6) 삭제
    dlist.delete_at(3)

    # Python 의 list 로 변환하여 출력
    print(list(dlist))

• ADT에서 언급한대로 리스트의 기능을 구현
• __len__(self) 를 구현하여 len 함수를 호출하면 리스트의 크기를 반환하도록 함
• __iter__(self) 와 __next__(self) 를 구현하여 이터레이터로서 동작하도록 구현.  for 문이나 list() 에 사용 가능.

 

단방향 연결 리스트나 원형 연결 리스트의 경우 양방향 연결 리스트의 코드를 조금 수정하는 것 만으로 구현할 수

있기 때문에 따로 구현하지 않는다.