자료구조 - 연결 리스트

리스트는 데이터에 순서를 매겨 늘어놓은 자료구조다. 

구조가 간단한 리스트로 선형 리스트(linear list) 또는 연결 리스트(linked list)가 있다.

 

위의 그림은 연결 리스트의 기본 구조다. A에서 F까지 데이터가 순서대로 나열되고 각 데이터가 화살표로 연결되어 있다. 이런 구조에서는 누군가를 건너뛰거나 뒤돌아 앞사람에게 연락해서는 안 된다.

연결 리스트에서 각각의 원소를 node라고 한다. 노드는 data와 pointer를 갖고 있다. 맨 앞에 있는 노드를 head node, 맨 끝에 있는 노드를 tail node라고 한다. 각 노드에서 바로 앞에 있는 노드를 predecessor node, 바로 뒤에 있는 노드를 successor node라고 한다.

 

 

배열로 연결 리스트 만들기

 

 

뒤쪽 노드 꺼내기

: 배열의 각 원소에는 순서대로 데이터가 저장되어 있다. 뒤쪽 노드를 꺼내기 위해선 인덱스 값이 1만큼 큰 원소에 접근하여 꺼낸다.

 

노드의 삽입과 삭제

: 예를 들어 새로운 원소 55이 새로 들어와서 12와 33 사이에 삽입해야 한다고 가정하자. 이 경우 삽입한 원소 이후의 모든 원소가 하나씩 뒤로 이동해야 한다. 따라서 데이터를 삭제/삽입할 때마다 데이터를 옮겨야 하므로 효율적이지 않다.

 

 

포인터를 이용한 연결 리스트

 

연결 리스트에 데이터를 삽입할 때 노드용 인스턴스를 생성하고, 데이터를 삭제할 때 노드용 인스턴스를 없애면 앞에서 제시한 데이터를 옮기는 문제를 해결할 수 있다. 

Node는 데이터용 필드 data와는 별도로 자신과 같은 클래스형의 인스턴스를 참조하기 위한 참조용 필드 next를 갖는다. 이처럼 자신과 같은 형의 인스턴스를 참조하는 필드가 있는 구조를 self-referential형이라고 한다.

 

연결 리스트에서 사용하는 Node

 

위 그림의 data는 데이터 자체가 아니라 '데이터에 대한 참조'이고 next는 '노드에 대한 참조'다.

 

 

뒤쪽 노드를 참조하는 필드 next를 뒤쪽 포인터라고 한다. 뒤쪽 포인터 next에는 뒤쪽 노드에 대한 참조를 저장한다. 뒤쪽 노드가 없는 꼬리 노드의 뒤쪽 포인터 값은 None이다.

 

다음 코드는 노드가 클래스 Node형이고, 연결 리스트를 클래스 LinkedList형으로 구현한 프로그램이다.

<code>

class Node:
    '''연결 리스트용 노드 클래스'''
    
    def __init__(self, data, next):
        self.data = data
        self.next = next
        
        
class LinkedList:
    '''연결 리스트 클래스'''
    
    def __init__(self):
        self.no = 0    # 노드의 개수
        self.head = None    # 머리 노드
        self.current = None    # 주목 노드
        
    def __len__(self):
        return self.no
    
    def search(self, data):
        """data와 값이 같은 노드를 검색"""
        cnt = 0
        ptr = self.head
        while ptr is not None:
            if ptr.data == data:
                self.current = ptr
                return cnt
            cnt += 1
            ptr = ptr.next
        return -1
    
    def __contains__(self, data):
        """연결 리스트에 data가 포함되어 있는지 확인"""
        return self.search(data) >= 0

    def add_first(self, data):
        '''맨 앞에 노드 삽입'''
        ptr = self.head
        self.head = self.current = Node(data, ptr)
        self.no += 1
        
    def add_last(self, data):
        '''맨 끝에 노드 삽입'''
        if self.head is None:
            self.add_first(data)
        else:
            ptr = self.head
            while ptr.next is not None:
                ptr = ptr.next
            ptr.next = self.current = Node(data, None)
            self.no += 1
            
    def remove_first(self):
        '''머리 노드 삭제'''
        if self.head is not None:
            self.head = self.current = self.head.next
        self.no -= 1
        
    def remove_last(self):
        '''꼬리 노드 삭제'''
        if self.head is not None:
            if self.head.next is None:    # 노드가 1개 뿐이라면
                self.remove_first         # 머리 노드를 삭제
            else:
                ptr = self.head    # 스캔 중인 노드
                pre = self.head    # 스캔 중인 노드의 앞쪽 노드
                
                while ptr.next is not None:
                    pre = ptr
                    ptr = ptr.next
                pre.next = None    # pre는 삭제 뒤 꼬리 노드
                self.current = pre
                self.no -= 1
            
    def remove(self, p):
        '''노드 p를 삭제'''
        if self.head is not None:
            if p is self.head:
                self.remove_first()
            else:
                ptr = self.head
                
                while ptr.next is not p:
                    ptr = ptr.next
                    if ptr is None:
                        return
                ptr.next = p.next
                self.current = ptr
                self.no -= 1
            
    def remove_current_node(self):
        '''주목 노드 삭제'''
        self.remove(self.current)
        
    def clear(self):
        '''전체 노드 삭제'''
        while self.head is not None:
            self.remove_first()
        self.current = None
        self.no = 0
        
    def print_current_node(self):
        '''주목 노드 출력'''
        if self.current is None:
            print('주목 노드가 존재하지 않습니다.')
        else:
            print(self.current.data)
        
    def print_all(self):
        '''모든 노드 출력'''
        ptr = self.head
        while ptr is not None:
            print(ptr.data)
            ptr = ptr.next     
            
# -- 이터레이터용 클래스 ~
    def __iter__(self):
        '''이터레이터를 반환'''
        return LinkedListIterator(self.head)
    
class LinkedListIterator:
    '''클래스 LinkedList의 이터레이터용 클래스'''
    def __init__(self, head):
        self.current = head
        
    def __iter__(self):
        return self
    
    def __next__(self):
        if self.current is None:
            raise StopIteration
        else:
            data = self.current.data
            self.current = self.current.next
            return data

 

 

 

str, list, tuple 등은 iterable(반복 가능)하다는 공통점이 있다. 이터러블 객체는 원소를 1개씩 꺼내는 구조의 객체이다.

이터러블 객체를 내장 함수인 iter() 함수에 인수로 전달하면 그 객체에 대한 iterator(반복자)를 반환한다.

 

이터레이터는 데이터가 줄지어 늘어선 것을 표현하는 객체이다. 이터레이터의 __next__()함수를 호출하거나, 내장 함수인 next() 함수에 반복자를 전달하면 줄지어 늘어선 원소를 순차적으로 꺼낸다. 꺼낼 원소가 없으면 StopIteration 예외 처리를 내보낸다.

클래스 LinkedList는 이터러블이 되도록 이터레이터를 구현한다. 이터레이터를 나타내는 것이 클래스 LinkedListIterator다.

 

파이썬은 리스트는 자료구조가 아니다.
: 연결 리스트는 임의의 위치에 원소를 삽입하거나 삭제할 때 빠르게 수행할 수 있다는 장점이 있다. 하지만 메모리와 속도 면에서는 배열보다 효율이 뒤떨어진다.
파이썬의 리스트는 이러한 연결 리스트의 자료구조가 아니라 모든 원소를 연속으로 메모리에 배치하는 '배열'로 내부에서 구현하고 있다. 그러므로 속도가 급격하게 떨어지지는 않는다. 또 원소를 하나식 추가/삽입할 때마다 내부에서 메모리를 확보하거나 해제하지 않는다. 실제 필요한 메모리보다 여유 있게 미리 마련해 놓기 때문이다.