연결리스트

연결리스트

위에서 각 노드들을 생성하여 서로 연결하는 작업을 해보았습니다.

 

이렇게 각 노드가 데이터와 포인터를 가지고

한줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조를 연결리스트라 합니다.

 

이 연결리스트는 리스트를 구현하는 방법 중 하나입니다.

 

위에서 보이는 것처럼

연결리스트중 맨 앞에 있는 노드를 머리 노드라 하며,

맨 끝에 있는 노드를 꼬리 노드라 합니다.

 

위 사진에서 머리노드는 A, 꼬리노드는 B가 되겠습니다.

 

 

 

 

 

 

 

 

 

연결리스트 구현

연결리스트역시 클래스로 구현합니다.

 

이 클래스안에는 2가지 종류의 속성이 포함되어 있습니다.

 

리스트에 등록되어있는 노드의 개수를 의미하는 no와

머리노드를 가리키는 head입니다.

 

 

메소드는

초기화하는 __init__메소드와

연결리스트에 포함된 노드 개수를 리턴하는 __len__이 있습니다.

 

그러면 연결리스트를 코드로 구현해보겠습니다.

 

class LinkedList:
	
    def __init__(self):
    	
        self.no = 0
        self.head = None
        
    def __len__(self):
    
    	return self.no

 

이렇게 연결리스트 클래스가 구현되었습니다.

 

아직 머리노드뿐만 아닌 어떤 노드도 존재하지 않으니

노드의 개수를 의미하는 속성 no는 0이며,

머리노드를 의미하는 속성인 head에는 None이 입력됩니다.

 

그렇다면 이 연결리스트 클래스를 호출하고

메소드도 호출해보도록 하겠습니다.

 

my_list = LinkedList()

print(len(my_list))

# 0이 출력된다.
# 아직 노드가 존재하지 않기 때문

 

 

 

자 그렇다면 노드를 삽입시키기 위해서는 어떻게 해야할까요?

 

클래스에 노드를 생성하는 메소드를 만들고

그 메소드를 호출시키면 됩니다.

 

 

 

 

 

 

 

 

add_first

이번에는 연결리스트의 맨 앞에 노드를 삽입하는 메소드를 생성해보도록 하겠습니다.

 

def add_first(self, data):
	
    ptr = self.head
    self.head = Node(data, ptr)
    self.no += 1

위 메소드는 새로운 머리노드를 생성하는 메소드라 봐도 무방합니다.

 

ptr이라는 변수에

기존의 머리노드인 self.head를 저장한 후

 

새롭게 들어온 data에 대한 노드의 next에 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이 꼬리노드가 될 때까지 while문을 반복
            
        ptr.next = Node(data, None)
        self.no += 1

 

이렇게 맨 끝에 새로운 꼬리노드를 삽입하는 메소드를 생성하였습니다.

 

위 과정을 시각적으로 표현해보겠습니다.

 

 

 

 

 

 

 

 

 

 

print

이번에는 연결리스트의 모든 노드를 출력하는

print 메소들를 생성해보도록 하겠습니다.

 

def print(self):

	ptr = self.head
    
    while ptr is not None:
    	print(ptr.data, end = '')
        
        if ptr.next is not None:
        	print('->', end = '')
        else:
        	print()
            
        ptr = ptr.next

 

위와 같이 ptr에 머리노드를 대입시키고

 ptr의 데이터를 출력시키면서 ptr에 다음 노드를 다시 대입합니다.

 

그리고 ptr의 다음 노드가 None일 때,

즉 ptr이 꼬리노드가 되었을 때 화살표 출력을 중지하고 

데이터 출력 후 while문을 종료합니다.

 

 

 

 

 

 

 

 

search

search 노드는

머리노드부터 꼬리노드까지 검색하면서

data와 같은 값이 있는지 확인합니다.

 

idx변수는 확인중인 노드의 인덱스이며,

검색 종료조건은 데이터에 맞는 노드를 찾았거나,

찾지 못하고 꼬리 노드에 도달하였을 때입니다.

 

그렇다면 search 메소드를 코드로 구현해보겠습니다.

 

def search(self, data):
	
    idx = 0
    ptr = self.head
    
    while ptr:  # ptr is not None 과 동일
    	if ptr.data == data:
        	return idx  # 조건에 맞는 노드의 인덱스 리턴
        ptr = ptr.next # 조건에 맞지 않는 노드이면 다음 노드로 다시 대입
        idx += 1  # 다음 노드의 인덱스로 변경
    return -1

만약 조건에 맞는 노드가 있다면 그 노드에 해당하는 index가 리턴될 것이며,

만약 없다면 -1이 리턴될 것입니다.

 

 

 

 

 

 

 

 

__contains__

이 메소드는 데이터의 포함 여부를 판단하는 함수입니다.

 

즉, 주어진 데이터와 값이 같은 노드를 포함하는지 판단하는 메소드입니다.

 

포함되어 있다면 True, 아니라면 False를 반환합니다.

 

def __contatins__(self, data):

	return self.search(data) >= 0

__contains__메소드는 search메소드를 이용합니다.

 

search메소드인 경우 주어진 데이터에 해당하는 노드의 index를 리턴하는 함수였습니다.

 

즉 주어진 데이터에 해당하는 노드의 인덱스는 0보다 큰값이며

노드를 포함한다면 True를 반환하고 

 

만약 없다면 search메소드에 -1이 반환되며

__contains__메소드에는 False가 반환될 것입니다.

 

 

 

 

여기에서 __contatins__메소드의 특징은

in 연산자로 호출할 수 있다는 것입니다. 

 

코드로 보여드리겠습니다.

my_list = LinkedList()

my_list.add_last('A')
my_list.add_last('B')
my_list.add_last('C')

print('A' in my_list)
print('D' in my_list)

# __contatins__메소드를 in 연산자로 호출
# 위에서 차례대로
# True
# False
#

 

이와 같이 in 연산자로 __contains__메소드를 호출할 수 있습니다.

 

 

 

 

 

 

 

 

 

연결리스트 삭제

지금까지는 연결리스트에 노드를 추가하는 것에대해 알아보았다면

이번에는 기존의 있던 노드를 삭제하는 메소드를 배워보겠습니다.

 

여기에서 노드를 삭제한다는 것은

실제로 그 노드를 제거한다는 느낌보다는

그 노드와 연결되어있는 길들을 모두 끊는 것을 의미합니다.

 

즉 그 노드로 가는 모든 길이 끊겼을 때

그 노드는 제거되었다고 표현합니다.

 

 

 

 

 

 

 

 

remove_first

이번에 만들어볼 메소드는

머리 노드를 삭제하는 함수입니다.

 

def remove_first(self):

	if self.head is not None:  # 리스트가 비어있지 않을 때
    	self.head = self.head.next
        self.no -= 1

 

위와 같이 머리노드와 그 다음 노드의 연결을 끊어

머리노드를 삭제하였습니다.

 

 

 

 

 

 

 

 

 

remove_last

이번에는 꼬리노드를 삭제하는 메소드를 만들어보겠습니다.

 

만약 노드가 1개만 존재한다면

머리 노드를 삭제하는 메소드인 remove_first로 넘겨준다.

 

지우는 방식은 리스트에 노드가 2개 이상 존재할 때

리스트의 맨 끝에서 노드를 삭제하는 방식입니다.

 

def remove_last(self):
	
    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.no -= 1

 

 

 

 

 

 

 

 

 

remove

임의의 노드를 삭제하는 메소드를 배워보겠습니다.

 

지금까지는 머리노드와 꼬리노드를 삭제하는 메소드를 알아보았다면

이번에는 노드를 지정하여 제거할 수 있는 메소드를 알아보겠습니다.

 

지정한 노드의 이름을 p라고 했을 때

p가 머리노드면 remove_first 메소드를 호출하고

 

p가 머리노드가 아니라면

p 이전 노드를 이용하여 p 노드를 삭제합니다.

 

def remove(self, p):

	if self.head is not None:
            if p is self.head:
                self.remove_first()  # p가 머리노드면 remove_first메소드 호출
            else:
                ptr = self.head

                while ptr.next is not p:  # 머리노드 부터 p노드를 찾는다.

                    ptr = ptr.next
                    if ptr is None:
                        return    # ptr이 리스트에 존재하지 않을 때

                ptr.next = p.next # ptr의 다음노드가 p이라면 
                                  # ptr의 다음노드를 p노드의 다음 노드와 연결한다.

                self.no -= 1

 

이와 같이 p노드의 이전 노드인 ptr을 이용하여

p노드의 연결을 끊어주었습니다.

 

 

 

 

 

 

 

 

 

remove_at

이번에는 index를 이용하여 노드를 삭제하는 메소드를 만들겠습니다.

 

삭제하는 방식은 index - 1의 위치를 찾은 후

index 위치의 노드를 삭제하는 방식입니다.

 

예를 들어 index 3에 위치한 노드를 제거하고 싶다면

index 2 위치의 노드를 찾아 그 뒤의 노드를 삭제하면 됩니다.

 

def remove_at(self, index):
	
    if index == 0:
    	self.remove_first() # 인덱스 0은 머리노드를 의미
    
    elif index < self.no:  # 인덱스가 노드의 개수보다 많은 경우를 방지
    	ptr = self.head  # 삭제할 노드의 이전 노드
        idx = 0  # ptr 노드의 인덱스
        
        while ptr is not None:
        	if idx == index - 1:  # 만약 지우고 싶은 노드의 위치를 찾으면
            	ptr.next = ptr.next.next  # ptr 다음 노드 삭제
                self.no -= 1
                break
            
            ptr = ptr.next 
            idx += 1

 

 

 

 

 

 

 

 

 

clear

이번에는 모든 노드를 삭제하는 메소드를 만들어보겠습니다.

 

지우는 방식은

연결 리스트가 비어 있을 때까지

머리 노드의 삭제를 반복합니다.

 

def clear(self):
	
    while self.head is not None:
    	self.remove_first()
        
    self.no = 0

 

이 방식으로 모든 노드를 삭제합니다.