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

---

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

---

 1. 연결 리스트 : 원소의 삽입 

def insert_at(self, pos, now_node):

 

pos가 가리키는 위치(1<= pos <= node_count + 1) 에 new_node를 삽입하고 성공/실패에 따라 True/False를 리턴한다. 

 

# 1. pos 위치의 바로 전 노드를 찾는다. 
prev = self.get_at(pos-1)

# 2. 새로운 노드의 next를 prev.next(prev 다음 노드)를 가리키게한다.
new_node.next = prev.next

# 3. prev.next가 새로운 노드를 가리키게 한다. 
prev.next = new_node

# 4. 새로운 노드를 삽입하였으므로 총 node_count 에 1이 추가된다. 
self.node_count += 1

 

✔ 코드 구현 주의 사항 

(1) 삽입하려는 위치가 리스트 맨 앞일 때

    ✔ prev 가 없다. 

    ✔ head 조정이 필요하다.  

 

(2) 삽입하려는 위치가 리스트 맨 끝일 때

    ✔ tail 조정이 필요하다. 

 

# (1) 삽입하려는 위치가 리스트 맨 앞일 때,
if pos == 1:
	new_node.next = self.head
    self.head = new_node


# (2) 삽입하려는 위치가 리스트 맨 끝일 때
if pos == self.node_count + 1:
	self.tail = new_node

 

연결리스트 원소 삽입의 복잡도

✔  맨 앞에 삽입하는 경우 : O(1)

✔  중간에 삽입하는 경우 :  O(N)

✔  맨 뒤에 삽입하는 경우:  O(1)

 

 2. 연결 리스트 : 원소의 삭제

def pop_at(self, pos):

 

pos가 가리키는 위치의 (1 <= pos <= node_count)  node를 삭제하고 그 node의 데이터를 Return 한다. 

 

✔ 코드 구현 주의 사항 

(1) 삭제하려는 node 위치가 리스트 맨 앞일 때

    ✔ prev 가 없다. 

    ✔ head 조정이 필요하다.  

 

(2) 삭제하려는  node의 위치가 리스트 맨 끝일 때

    ✔ tail 조정이 필요하다. 

 

삭제하려는 노드가 마지막 노드인 경우 즉, pos == node_count 일 때 pos가 가리키는 노드 tail 이전의 노드 인 prev를 찾을 방법이 없으므로 앞에서 부터 순차적으로 찾아야 한다. 

 

연결리스트 원소 삭제의 복잡도

✔  맨 앞에서 삭제하는 경우 : O(1)

✔  중간에서 삭제하는 경우 :  O(N)

✔  맨 끝에서 삭제하는 경우:  O(N)

 

 3. 연결 리스트 :  두 리스트의 연결

def concat(self, L):
	self.tail.next = L.head
    
    # L이 빈 리스트인 경우 예외처리
    if L.tail:
    	self.tail = L.tail
    
    self.node_count += L.node_count

 

[ 문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 insertAt(self, pos, newNode):
        if pos < 1 or pos > self.nodeCount + 1:
            return False

        if pos == 1:
            newNode.next = self.head
            self.head = newNode

        else:
            if pos == self.nodeCount + 1:
                prev = self.tail
            else:
                prev = self.getAt(pos - 1)
            newNode.next = prev.next
            prev.next = newNode

        if pos == self.nodeCount + 1:
            self.tail = newNode

        self.nodeCount += 1
        return True


    def popAt(self, pos):
        curr = 0

        # 예외1. pos가 인덱스 밖의 범위에 있는 경우 
        if pos < 1 or pos > self.nodeCount:
            raise IndexError
        # 예외2.연결리스트 길이가 1인 경우 
        if self.nodeCount == 1:
            curr = self.head
            self.head, self.tail = None, None
        
        # 예외 1,2에 해당하지 않는 경우 
        else:
            # pos 가 head 위치인 경우  --> head 조정 필요
            if pos == 1:
                curr = self.head
                self.head = curr.next

            # pos 가 tail 위치인 경우 --> tail 조정 필요
            if pos == self.nodeCount:
                prev = self.getAt(pos-1)
                curr = prev.next
                prev.next = None
                self.tail = prev

            # 그 외의 경우
            if 1 < pos < self.nodeCount:
                prev = self.getAt(pos-1)
                curr = prev.next
                prev.next = curr.next

        self.nodeCount -= 1
        return curr.data




    def traverse(self):
        result = []
        curr = self.head
        while curr is not None:
            result.append(curr.data)
            curr = curr.next
        return result


def solution(x):
    return 0