링크드 리스트의 구현 및 연산 - 파이썬(Python)

링크드 리스트의 구현 (Node, __init__, __str__)

 

링크드 리스트를 구현하기 위해선, 각각의 데이터와 다음 데이터에 대한 주소(레퍼런스)를 저장할 '노드' 객체가 필요하다.

 

class Node:
	def __init__(self, data):
    	self.data = data # 파라미터로 받은 데이터를 저장
        self.next = None # 기본값은 None으로 지정 후 추후 다른 노드들과 연결
        
node_1 = Node(2)
node_2 = Node(3)
node_3 = Node(5)
node_4 = Node(7)

 

노드 클래스를 생성 후, 데이터가 각각 2, 3, 5, 7인 네 개의 링크드 리스트 노드를 생성해주었다.

 

node_1.next = node_2
node_2.next = node_3
node_3.next = node_4

 

이후 각 노드의 next를 정의해줌으로써 이 네 개의 노드를 서로 연결되게 되었다.

 

이제 맨 앞의 node_1의 주소만 알 수 있다면 node_4 까지 접근할 수 있게 된 것이다.

 

알 수 있다시피, 링크드 리스트의 데이터들에 접근하기 위해서 맨 앞의 값은 매우 중요하다.

 

따라서 이 맨 앞의 시작값을 링크드 리스트라는 객체에 저장해준다.

 

또한, 추가 연산 등의 실행을 용이하게 하기 위해서 맨 뒤의 값 또한 링크드 리스트 객체에 저장해준다.

 

class LinkedList:
	def __init__(self):
    	self.head = None # 링크드 리스트의 맨 앞에 위치하는 값
        self.tail = None # 링크드 리스트의 맨 뒤에 위치하는 값


linked_list = LinkedList()

linked_list.head = node_1
linked_list.tail = node_4

 

정의된 링크드 리스트를 호출했을 때 저장된 값들을 명확하게 확인하기 위해서 __str__를 다음과 같이 정의해줄 수 있다.

 

class LinkedList:
	def __init__(self):
    	self.head = None # 링크드 리스트의 맨 앞에 위치하는 값
        self.tail = None # 링크드 리스트의 맨 뒤에 위치하는 값
        
	
    def __str__(self):
    	res_str = '|'
        iterator = self.head
        
        while iterator: # 맨 앞의 값부터 맨 끝의 노드까지 돈다
        	res_str += f" {iterator.data} |" 
            iterator = iterator.next # iterator.next == None이라는 것은 iterator가 tail이라는 것
            
		return res_str
        

 

 

위 정의된 linked_list를 출력하면 다음과 같은 값이 나온다.

 

링크드 리스트의 연산 (탐색, 추가, 삭제)

 

1) size 연산 - 링크드 리스트에 저장된 데이터들의 갯수 확인

 

# 링크드 리스트의 size 연산

def size(self):
	iterator = self.head
    size = 0
    
    while iterator != None: # 모든 노드를 다 돌 때까지
    	iterator = iterator.next
        size += 1
        
    return size
    

 

1) search_with_data 연산 - 특정 데이터를 가진 노드가 리스트에 있는지 확인

 

# 링크드 리스트의 serach_with_data 연산

def search_with_data(self, data):
	iterator = self.head
    
    while iterator: # iterator가 링크드 리스트의 첫 값부터 끝 값까지 돌면서
    	if iterator.data == data: # 파라미터로 주어진 데이터와 일치하는 데이터가 있는지
        	return iterator # 있다면 해당 노드를 리턴
		
        iterator = iterator.next
    
	return None # 데이터를 찾지 못하고 while문을 빠져나올시 None을 리턴

 

2) search_with_index 연산 - 특정 인덱스에 위치한 노드를 확인

 

# 링크드 리스트의 search_with_index 연산

def search_with_index(self, index):
	iterator = self.head
    size = self.size() # 링크드 리스트에 저장된 데이터의 갯수 확인
    
    if index > size:
    	return None
	
    else:
    	for _ in range(index):
        	iterator = iterator.next
            
        return iterator
    
		

 

 

2) append 연산 - 링크드 리스트의 맨 뒤에 새로운 노드를 추가해준다.

 

# 링크드 리스트 append 연산 

def append(self, data):
	new_node = Node(data) # 파라미터로 받은 데이터를 갖는 노드를 만들어준다
    
    if self.head == None: # 현재 리스트에 아무 값도 없을 경우 새 노드를 head와 tail로 저장
    	self.head = new_node
        self.tail = new_node
        
	else: # 기존 맨 뒤의 값의 next를 새 노드로 설정해준 후 리스트의 tail을 새 노드로 설정해준다.
    	self.tail.next = new_node 
        self.tail = new_node
    	

 

3) prepend 연산 - 링크드 리스트의 맨 앞에 새로운 노드를 추가해준다.

 

# 링크드 리스트의 prepend 연산

def prepend(self, data):
	new_node = Node(data) # 새로운 노드 생성
    
    if self.head == None: # 리스트가 비어있을 경우 새 노드를 모두 head와 tail로 설정
    	self.head = new_node
        self.tail = new_node
        
	else: # 새 노드의 next를 기존의 head 노드로 설정 후 리스트의 head를 새 노드로 설정 
    	new_node.next = self.head
        self.head = new_node

 

4) insert_after - 특정 노드의 다음 자리에 새로운 노드를 추가

 

# 링크드 리스트의 insert_after 연산

def insert_after(self, prev_node, data): # 삽입될 위치의 이전 노드와 삽입할 데이터를 파라미터로
	new_node = Node(data)
    
	if prev_node != None:
    	if prev_node == self.tail: # 이전 노드가 tail노드이면 append 메서드를 이용
        	self.append(data)
		
        else:
    		new_node.next = prev_node.next
        	prev_node.next = new_node
	
    else: # 만약 파라미터로 입력된 prev_node가 잘못된 값일 경우
    	return None

 

 

 

4) pop 연산 - 링크드 리스트의 맨 뒤 값을 삭제 후 삭제된 값 return

 

# 링크드 리스트의 pop 연산

def pop(self):
	
    if self.head == None: # 리스트가 비어있을 때 None 리턴
    	return None
    
	iterator = self.head.next
    prev = self.head
    
    data_to_pop = self.tail # 삭제된 값을 리턴해주기 위해 미리 저장
    
    while iterator.next != None:
    	iterator = iterator.next
        prev = prev.next
        
	# while문을 빠져나오면 iterator에는 self.tail이, prev에는 self.tail 이전의 값이 저장된다.
    
    # 리스트의 tail을 prev로 저장 후 prev의 next를 None으로 해줌으로써 기존 tail과의 연결을 끊어준다.
    self.tail = prev
    prev.next = None
    
    return data_to_pop

 

5) popleft 연산 - 링크드 리스트의 맨 앞 값을 삭제 후 삭제된 값 return

 

# 링크드 리스트의 popleft 연산

def popleft(self):
	
    if self.head == None: # 리스트가 비어있을 때
    	return None
        
	data_to_pop = self.head
    self.head = self.head.next # 리스트의 헤드값을 바꿔주기만 하면 된다.
    
    return data_to_pop

 

6) delete_after 연산 - 특정 노드의 다음 값을 삭제 후 삭제된 값 return

 

# 링크드 리스트의 delete_after 연산

def delete_after(self, prev_node):
	if prev_node != None:
    	if prev_node.next == tail: # 삭제하고자 하는 값이 tail노드일 때
        	prev_node.next = None
            self.tail = prev_node
        
        elif prev_node == tail: # 이전 값이 tail노드로 삭제할 위치에 노드가 존재하지 않을 때
        	return None
        
        else: # 노드가 다른 노드들 사이에 존재할 때
        	prev_node.next = prev_node.next.next
	
    else: # 입력된 prev_node의 값이 잘못되었을 때
    	return None