[Python] 링크드 리스트(Linked List)

💡  본 내용은 코드잇 기본 자료구조들 강의 및 신찬수 교수님의 자료구조 강의를 들고 요약한 내용입니다.

 

내용이 부족하거나 잘 못 될 수 있습니다.

추후 계속 공부하면서 수정하겠습니다~!!

 

링크드 리스트(Linked List)

• 데이터를 순서대로 저장해준다.
• 요소를 계속 추가할 수 있다.(동적 배열처럼)

연결된 박스(노드)들의 순서:

규리 → 태호 → 동욱 →유나 → 현승 

 

 

 

👉프로그래밍적으로 생각

노드(Node): 데이터와 Next 의 객체이다.

연속적으로 되어 있는 것이 아닌 실제 메모리에는 ★흩어져★ 있다.

 

 

 

# ------------- 간단한 링크 노드 -------------------
class Node:
	"""링크드 리스트의 노드 클래스"""
    def __init___(self, data):
    	self.data = data	# 노드가 저장하는 데이터
        self.next = None	# 다음 노드에 대한 레퍼런스
               
# 데이터 2, 3, 5, 7, 11을 담는 노드들 생성
# 지금은 각 노드끼리 아무런 관계가 없다.
head_node = Node(2)
node_1 = Node(3)
node_2 = Node(5)
node_3 = Node(7)
tail_node = Node(11)

# -------------- 간단한 링크드 리스트 -------------------
# 노드 연결
head_node.next = node_1
node_1.next = node_2
node_2.next = node_3
node_3.next = tail_node

# 노드 순서대로 출력
iterator = head_node

while iterator is not None:
	print(iterator.data)
    iterator = iterator.next

# ---------------- 링크드 리스트 클래스 및 추가 연산 ---------------------
# 헤드에 해당하는 노드가 고정되면 더 이상 변동 X
# tail은 뒤이어 추가되는 노드로 변동 
# tail.next(해당 노드의 next)는 다음 노드를 가리키고 있다.

class Node:
	"""링크드 리스트의 노드 클래스"""
    def __init___(self, data):
        self.data = data	# 노드가 저장하는 데이터
        self.next = None	# 다음 노드에 대한 레퍼런스

class LinkedList:
	"""링크드 리스트 클래스"""
    
    def __init__(self):
    	self.head = None
        self.tail = None
        
    def append(self, data):	# 인스턴스 메소드
    	"""링크드 리스트 추가 연산 메소드"""
        new_node = Node(data)
        
        if self.head is None:	# 인스턴스 헤드가 None 이면(비어있으면)
            self.head = new_node
            self.tail = new_node
        else:	# 링크드 리스트가 비어있지 않으면
            self.tail.next = new_node
            self.tail = new_node
            
            
# 새로운 링크드 리스트 생성
my_list = LinkedList()

# 링크드 리스트에 데이터 추가
my_list.append(2)
my_list.append(3)
my_list.append(5)
my_list.append(7)
my_list.append(11)
        
# 링크드 리스트 출력
iterator = my_list.head

while iterator is not None:
    print(iterator.data)
    iterator = iterator.next

 

👉링크드 리스트 __str__ 메소드

def __str__(self) -> str:
        """링크드 리스트를 문자열로 표현해서 리턴하는 메소드"""
        res_str = "|"

        # 링크드 리스트 안에 모든 노드를 돌기 위한 변수
        # 가장 앞 노드로 정의
        iterator = self.head

        # 링크드 리스트 끝까지 돈다.
        while iterator is not None:
            # 각 노드의 데이터를 리턴하는 문자열에 더 해준다.
            res_str += f" {iterator.data} |"
            iterator = iterator.next    # 다음 노드로 넘어간다.

        return res_str

 

👉링크드 리스트 ★접근 연산★

• 배열과 같이 인덱스로 링크드 리스트에 접근이 가능하다.
• 단, 특정 위치에 있는 노드를 리턴하는 연산!
• 배열은 주소로 바로 값에 접근이 가능하지만, 레퍼런스로 접근

def find_node_at(self, index):
        """링크드 리스트 접근 연산 메소드. 파라미터 인덱스는 항상 있다고 가정"""
        iterator = self.head
        
        for _ in range(index):
            iterator = iterator.next

        return iterator

 

👉링크드 리스트 접근 시간 복잡도

• 인덱스 x에 있는 노드에 접근하려면 head에서 다음 노드로 x번 가면 됨!
• 마지막 노드에 접근하려면 head 에서 다음 노드로 n -1 번 가야 됨

 

👉 링크드 리스트 ★탐색 연산★

# 탐색연산
def find_node_with_data(self, data):
    """링크드 리스트에서 탐색 연산 메소드. 단, 해당 노드가 없으면 None을 리턴한다"""
    # 코드를 쓰세요
    iterator = self.head # nod

    while iterator.data != data:
        iterator = iterator.next
        if iterator is None:
            return None
    return iterator

 

👉 링크드 리스트 ★삽입 연산★

def insert_after(self, previous_node, data):
    """링크드 리스트 주어진 노드 뒤 삽입 연산 메소드"""
    new_node = Node(data)

    # tail 노드 다음에 노드를 삽입할 때
    if previous_node is self.tail:
        self.tail.next = new_node
        self.tail = new_node
    else: # 두 노드 사이에 삽입할 때
        new_node.next = previous_node.next
        previous_node.next = new_node

 

 

👉 링크드 리스트 가장 앞 삽입

내가 푼 결과랑 정답과 똑같아서 행복하다.

def prepend(self, data):
    """링크드 리스트의 가장 앞에 데이터 삽입"""
    # 코드를 쓰세요

    # 노드를 생성
    new_node = Node(data)

    # 링크드 리스트가 비어있으면
    if self.head is None:
        self.head = new_node
        self.tail = new_node
    else:   # 링크드 리스트가 비어있지 않으면
        new_node.next = self.head
        self.head = new_node

 

👉 링크드 리스트 삭제

def pop_left(self):
    """링크드 리스트의 가장 앞 노드 삭제 메소드. 단, 링크드 리스트에 항상 노드가 있다고 가정한다"""
    # 코드를 쓰세요

    # 가장 앞 노드 데이터
    data = self.head.data

    if self.head is self.tail:
        self.head = None
        self.tail = None
    else: 
        self.head = self.head.next

    return data

 

 

더블 링크드 리스트

• 싱글리 링크드 리스트에서 안 바꿔도 되는 메소드
  • find_node_at(접근 연산)
  • find_node_with_data(탐색 연산)
  • __str__  메소드

 

👉 더블 링크드 리스트 ★삽입 연산★

   def insert_after(self, previous_node, data):
        """링크드 리스트 추가 연산 메소드"""
        # 코드를 쓰세요
        
        # 새로운 노드로
        new_node = Node(data)
        
        # tail 노드 다음에 노드를 삽입할 때
        if previous_node is self.tail:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node
        
        else:
            # 새롭게 생성한 노드를 이미 있는 링크드 리스트에 연결시키고
            new_node.prev = previous_node 
            new_node.next = previous_node.next
    
            # 이미 있는 노드들의 앞과 다음 레퍼런스를 새롭게 생성한 노드로 지정한다
            previous_node.next.prev = new_node
            previous_node.next = new_node