[프로그래머스 강의] 7강 연결리스트(Linked List) (1)

---

'어서와! 자료구조와 알고리즘은 처음이지?'

 

퇴근하고 공부하는게 쉽지 않은 거 같지만 그래도 강의 들으면서 하니까

책 보면서 하는 거 보다는 훨씬 나은 거 같다,, 👀

---

 

연결리스트(Linked List)

연결리스트에 각각 연결되어 있는 노드는 Data 와 Next 를 갖는다. Node 내의 데이터는 다른 구조로 이루어 질 수 있다. 예를 들어 문자열, 레코드, 또 다른 연결리스트가 가능하다.

 

# Node 클래스 정의

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

 

특정 원소 참조

class Node:
    def __init__(self, item):
        self.data = item
        self.next = None
        self.node_count = 0
    
    # 특정 원소 참조 
    def get_at(self, pos):
        if pos <= 0 or pos > self.node_count:
            return None
        
        i = 1
        curr = self.head
        while i < pos:
            curr = curr.next
            i += 1
        return curr

 

배열과 비교한 연결 리스트

	배열	연결리스트
저장공간	연속한 위치	임의의 위치
특정원소지칭	O(1)	O(n)

 

원소의 삽입/삭제 시 연결리스트의 경우 링크를 끊어 원소를 삽입 하거나 삭제할 수 있어 빠른 시간 O(1)에 처리가 가능한 반면 선형 배열의 경우 삽입, 삭제 시 O(n) 만큼의 시간을 소요한다. 연결 리스트는 선형 배열에 비해서 데이터 구조 표현에 소요되는 저장공간(메모리) 소요가 크다. 링크 또한 메모리에 저장되어야 하므로, 동일한 데이터 원소들을 담기 위하여 사용하는 메모리 요구량이 크다. 

 

[문 1. 연결 리스트 순회 ]

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

class LinkedList:
    def __init__(self):
        self.nodeCount = 0
        self.head = None
        self.tail = None

    def getAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            return None
        i = 1
        curr = self.head
        while i < pos:
            curr = curr.next
            i += 1
        return curr

    def traverse(self):
        answer = []
        
        # 새로 노드 포인터 curr 지정해 줘야 에러가 안난다. 
        curr = self.head
        while curr != None:
            answer.append(curr.data)
            curr = curr.next
        
        return answer


# 이 solution 함수는 그대로 두어야 합니다.
def solution(x):
    return 0