[자료구조/Python] 복습 2. LinkedList

LinkedList

데이터를 링크로 연결해서 관리하는 자료구조

자료의 순서는 정해져 있지만, 메모리상의 연속성은 보장되지 않는다

노드라는 구조체로 이루어진 자료구조, 노드는 데이터와 다음 데이터의 주소를 담고 있다.

• 장점
  • 데이터 공간을 미리 할당 받지 않아도 된다
  • 리스트 길이가 가변적이라서 추가,삭제가 용이하다
• 단점
  • 주소를 저장하는 추가 공간이 필요하다.
  • 연결 정보를 찾는 시간이 필요하기 때문에 접근 속도가 상대적으로 느리다
  • 데이터 추가, 삭제 시 앞 뒤 데이터의 연결을 재구성하는 작업이 필요하다

노드 : 데이터 저장 단위로, 값 + 포인터로 구성

LinkedList 연산

작업을 수행하는 위치(head, 중간, tail)에 따라 연결 작업이 다르다.

 

데이터 추가

• head로 추가할 때
  • 추가할 데이터를 담을 노드 생성
  • 링크 연결 작업
  • head 이전 작업
• tail에 추가할 때
  • 추가할 데이터를 담을 노드 생성
  • head로부터 끝노드까지 순회
  • 끝 노드의 포인터에 생성한 노드의 주소 연결
• 중간에 추가할 때
  • 추가할 데이터를 담을 노드 생성
  • head로부터 데이터 추가 위치 직전 노드까지 순회
  • 링크 연결 작업(이전노드의 포인터를 지금 노드에, 지금 노드의 포인터를 다음 노드의 위치로 연결)

데이터 삭제

• head 위치의 노드 삭제할 때
  • 삭제 대상 노드 지정(delete_node)
  • head 이전 작업
  • delete_node 삭제
• tail 위치의 노드 삭제할 때
  • head로 부터 가장 끝까지 순회
  • 끝 노드 삭제
  • 삭제 이전 노드의 링크 처리
• 중간에 있는 노드 삭제할 때
  • head로부터 삭제 대상 노드까지 순회 및 해당 노드(delete_node) 지정
  • 삭제 대상 이전/이후 노드의 링크 연결 작업
  • delete_node 삭제

구현

참고 블로그

• 노드 생성

class Node :
    def __init__(self, data):
        self.data = data
        self.next = None

• 가장 오른쪽에 노드 추가하기

# 가장 오른쪽에 노드 추가하기 
    def append(self, data):
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = None(data)

• 전체 데이터 출력

# 전체 데이터 출력  
    def print_all(self):
        cur = self.head
        while cur.next is not None:
            print(cur.data, end = ' ')
            cur = cur.next

• 원하는 노드 찾기

def get_node(self, index):
        count = 0
        node = self.head
        while count < index:
            count += 1
            node = node.next
        return node

• 중간에 노드 삽입 (헤드인 경우 항상 고려하기!)

def add_node(self, index, value) :
        new_node = Node(value)
        if index == 0:
            new_node.next = self.head
            self.head = new_node
            return
        
        node = self.get_node(index - 1)
        next_node = node.next
        node.next = new_node
        new_node.next = next_node

• 노드 삭제 (헤드인 경우 항상 고려하기!)

def delete_node(self, index):
        if index == 0:
            self.head = self.head.next
            
        prev_node = self.get_node(index - 1)    
        prev_node.next = self.get_node(index) .next (prev_node.next.next)