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

---

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

 

드디어 금요일이다........! 😆

---

 

연결리스트 장점

삽입과 삭제가 유연하다는 것이 가장 큰 장점 ! 

 

"특정 원소의 바로 다음"을 지정하여 원소를 삽입/삭제 하는 연산 정의

# 새로운 메서드 

def insert_after(prev, newNode): #--> prev 노드 뒤에 newNode 삽입
def pop_after(prev): # --> prev 노드 뒤에 노드 삭제

 

 

맨 앞에 원소를 삽입하거나 삭제하는 연산을 이전과 동일한 방식으로 해결하기 위해 연결 리스트의 맨 앞에다가 데이터 원소를 담고 있지 않은 그냥 자리만 차지하는 노드인 더미 노드(dummy node)를 추가한다. 

 

# head가 가리키는 부분이 데이터를 담고 있지 않은 Node(None) 임을 확인하자 

class LinkedList:
	def __init__(self):
    	self.node_count = 0
        self.head = Node(None)
        self.tail = None
        self.head.next = self.tail

 

리스트 순회

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

 

K번째 원소 반환하기

def get_at(self, pos):  # get_at(0) --> head
	if pos < 0 or pos > self.node_count:
    	return None
    
    i = 0
    curr = self.head
    
    while i < pos:
    	curr = curr.next
        i += 1
    
    return curr

 

원소의 삽입

prev가 가리키는 node의 다음에 new_node를 삽입하고 성공/실패에 따라 True/False를 리턴한다. 

 

def insert_after(self, prev, new_node):
	new_node.next = prev.next
    
    # tail 조정
    if prev.next is None:
    	self.tail = new_node
    prev.next = new_node
    self.node_count += 1
    return True

 

insert_at() 의 구현 

insert_after()을 호출하여 insert_at 을 구현해본다. 

 

✔ pos 범위조건 확인한다.

✔ pos == 1 인 경우에는 head 뒤에 new_node 삽입한다.

✔ pos == node_count + 1인 경우에는 tail 이 prev이다.

✔ 그렇지 않은 경우에는 prev 는 get_at(..) 으로 구한다.

 

def insert_at(self, pos, newNode):
	if pos < 1 or pos > self.node_count + 1
    	return False
    
    if pos != 1 and pos == self.node_count + 1:
    	prev = self.tail
    else:
    	prev = self.get_at(pos-1)
    
    
    return self.insert_after(prev, new_node)

 

원소의 삭제

prev 다음 node를 삭제하고 그 node의 data를 출력한다.

 

주의!

(1)  prev가 마지막 노드일 때 prev.next == None

    ✔ 삭제할 node 없음

    ✔ return None

 

(2) 리스트 맨 끝의 node를 삭제할 때 ( curr.next == None)

    ✔ tail 조정 필요

 

두 리스트 연결

def concat(self, L):
	self.tail.next = L.head.next
    
    if L.tail:
    	self.tail = L.tail 
    
    self.node_count + = L.node_count

 

[ 문1. dummy node를 가지는 연결리스트 노드 삭제 ]

class Node:

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


class LinkedList:

    def __init__(self):
        self.nodeCount = 0
        self.head = Node(None)
        self.tail = None
        self.head.next = self.tail

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

    def getAt(self, pos):
        if pos < 0 or pos > self.nodeCount:
            return None

        i = 0
        curr = self.head
        while i < pos:
            curr = curr.next
            i += 1

        return curr

    def insertAfter(self, prev, newNode):
        newNode.next = prev.next
        if prev.next is None:
            self.tail = newNode
        prev.next = newNode
        self.nodeCount += 1
        return True

    def insertAt(self, pos, newNode):
        if pos < 1 or pos > self.nodeCount + 1:
            return False

        if pos != 1 and pos == self.nodeCount + 1:
            prev = self.tail
        else:
            prev = self.getAt(pos - 1)
        return self.insertAfter(prev, newNode)

    def popAfter(self, prev):
        curr = 0
        
        # 맨 끝의 노드를 삭제하려는 경우 
        if prev.next == self.tail:
            curr = prev.next
            prev.next = None
            self.tail = prev

        else:
            curr = prev.next
            prev.next = curr.next

        self.nodeCount -= 1
        return curr.data

    def popAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            raise IndexError
        
        else:
            prev = self.getAt(pos-1)
            return self.popAfter(prev)
            
def solution(x):
    return 0