자료구조와 함께 배우는 알고리즘][리스트] - 포인터를 이용한 연결 리스트

1. 포인터를 이용한 연결 리스트란?

노드마다 뒤쪽 노드를 가리키는 포인터가 포함되도록 구현하는 연결 리스트를 포인터를 이용한 연결리스트라고 한다.

 

 

 

2. 포인터로 연결 리스트 만들기

📌출처: https://miro.medium.com/max/1030/1*YxP9qaa7DeDBaRepONXzPQ.png

• 연결 리스트에 데이터를 삽입할 때 노드용 인스턴스를 생성하고, 데이터를 삭제할 때 노드용 인스턴스를 없애면 앞에서 제시한 데이터를 옮기는 문제를 해결할 수 있다. 
• Node는 데이터용 필드 data와 별도로 자신과 같은 클래스형의 인스턴스를 참조하기 위한 참조용 필드 next를 갖는다. 이처럼 같은 형의 인스턴스를 참조하는 필드가 있는 구조를 자기 참조형이라고 한다. 

 

 

 

3. 포인터로 연결 리스트 구현하기

#포인터로 연결 리스트 구현하기

class Node:
    def __init__(self,data):
        #초기화
        self.data = data
        self.next = next

Node 클래스

• 노드 클래스 Node에는 다음과 같이 필드와 __init__( )함수가 있다.

 

__init__( )함수

• __init__( )함수는 전달받은 data와 next를 해당 필드에 대입한다.
• 호출할 때 어떤 인수도 생략할 수 있고, 생략할 경우 None으로 간주한다.

 

 

 

파이썬의 리스트는 자료구조가 아니다.

파이썬에서 리스트는 연결 리스트의 자료구조가 아니라 모든 원소를 연속으로 메모리에 배치하는 '배열'로 내부에서 구현하고 있다. 그러므로 속도가 급격히 떨어지지는 않는다. 또 원소를 하나씩 추가, 삽입할 때마다 내부에서 메모리를 확보하거나 해제하지 않는다. 실제 필요한 메모리보다 여유있게 미리 마련해 놓기 때문이다.

 

4. 연결 리스트 클래스

#연결 리스트 클래스

class LinkedList:
    
    def __init__(self):
        #빈 리스트 생성
        #초기화
        self.no = 0 # 노드의 개수
        self.head = None # 머리 노드
        self.current = None # 주목 노드

    def __len__(self):
        # 노드 개수를 반환
        # 연결 리스트의 노드 개수를 반환
        return self.no

연결 리스트의 필드

• no: 리스트에 등록되어 있는 노드의 개수
• head: 머리 노드에 대한 참조 
• current: 현재 주목하고 있는 노드에 대한 참조이며, 리스트에서 노드를 검색하여, 그 노드를 주목한 직후에 노드를 삭제하는 등의 용도로 사용한다.

 

 

빈 연결 리스트

head is None #연결 리스트가 비어있는지 확인

 

 

노드가 1개인 연결 리스트

head.next is None

 

 

노드가 2개인 연결 리스트

head.next.next is None

 

 

꼬리 노드의 판단

p.next is None

 

 

검색을 수행하는 search( ) 함수

def search(self,data):
    #data와 값이 같은 노드를 검색
    cnt = 0
    ptr = self.head

    while prt 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

 

 

머리에 노드를 삽입하는 add_first( ) 함수

def add_first(self,data):
    #맨 앞에 노드 삽입
    ptr = self.head
    self.head = self.current = Node(data,ptr)
    self.no += 1

 

 

꼬리에 노드를 삽입하는 add_last( ) 함수

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