4. 원소 삽입

5. 원소 삭제

6. 두 리스트 합치기

---

원소의 삽입

• def insertAt(self, pos, newNode):
• pos가 가리키는 위치에 (1 <= pos <= nodeCount + 1)
• newNode를 삽입하고
• 성공/실패 에 따라 True/False 를 리턴

• 이전 노드의 위치를 확인
  • prev = self.gerAt(pos - 1)
• 새로 추가되는 노드의 위치를 이전노드의 다음노드(next)로 위치 지정
  • newNode.next = prev.next
• 새로 추가되는 노드의 값을 이전노드의 다음노드(next)의 값으로 저장
  • prev.next = newNode
• 노드의 카운트를 +1
  • nodeCount += 1

예외 케이스

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

→ prev가 없음

→ Head 조정 필요

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

→ Tail 조정 필요

3. 빈 리스트에 삽입할 때

→ 1. 2. 번의 두 조건을 활용하여 처리

linkedlist.py > def insertAt(self, pos, newNode):

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

        if pos == 1:    # newNode가 즉,node넣으려는 위치가 맨 처음일경우
            newNode.next = self.head    # prev는 없고, next위치를 새로지정
            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.nodeCount += 1
            self.tail = newNode
        return True

연결 리스트 테스트 실행

Python 3.7.3 (default, Mar  6 2020, 22:34:30)
[Clang 11.0.3 (clang-1103.0.32.29)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> from linked_list import *
>>> a = Node(67)
>>> b = Node(34)
>>> c = Node(28)
>>> L = LinkedList()
>>> L
LinkedList: empty
>>> L.insertAt(1, a)
True
>>> L.insertAt(2, b)
True
>>> L.insertAt(1, c)
True
>>> L
28 -> 67 -> 34
>>> N = Node(99)
>>> L.insertAt(2, N)
True
>>> L
28 -> 99 -> 67 -> 34
>>>

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

• 맨 앞에 삽입하는 경우 : O(1)
• 중간에 삽입하는 경우 : O(n)
• 맨 끝에 삽입하는 경우 : O(1)

---

원소의 삭제

• def posAt(self, pos):
• pos가 가리키는 위치의 (1 <= pos <= nodeCount)
• node를 삭제하고
• 그 node의 데이터를 리턴

예외 케이스

1. 삭제하려는 node가 맨 앞의 것일 때

→ prev 가 없읍

→ Head 조정 필요

2. 리스트 맨 끝의 node를 삭제할 때

→ Tail 조정 필요

3. 유일한 노드를 삭제할 때

→ 1. 2. 두 조건 활용하여 처리

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

• 맨 앞에 삭제하는 경우 : O(1)
• 중간에 삭제하는 경우 : O(n)
• 맨 끝에 삭제하는 경우 : O(1)

---

두 리스트의 연결

• def concat(self, L)
• 연결 리스트 self의 뒤에 또다른 연결 리스트인 L을 이어 붙임

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

[실습] 연결 리스트 노드 삭제

문제

어서와! 자료구조와 알고리즘은 처음이지? 8강 실습: 연결 리스트 노드 삭제하기

문제 설명

제 8 강에서 소개된 추상적 자료구조 LinkedList 클래스의 메서드로서 popAt() 메서드를 강의 내용에 소개된 요구조건을 만족시키도록 구현하세요.

초기 코드로 들어 있는 것은 solution() 함수를 포함하여 다른 부분은 수정하지 말고, def popAt(self, pos): 의 메서드 몸체만 구현하세요.

만약, 인자로 주어진 pos 가 올바른 범위의 값을 가지지 않는 경우에는 IndexError exception 을 발생시키도록 합니다. 이렇게 하기 위한 코드는 raise IndexError 입니다.

*** 2020년 3월 23일, 학습자의 질문에 답하면서 보니 특정한 경우의 정확성을 올바르게 검증하지 못하는 경우가 발견되어 테스트 케이스 4 번을 추가했습니다.

---

나의 풀이

• pos가 가르키는 위치 확인 (1 <= pos <= nodeCount)
• 반대로 pos가 가르키지 않는 부분 확인 (pos < 1 or pos > self.nodeCount)
  • IndexError 처리
• pos가 1 이라면(첫 번째 노드 삭제 케이스)
  • 그리고 nodeCount가 1이라면(노드가 1 밖에 없는 케이스)
    • head와 tail : None
    • nodeCount : 0
• pos가 1 이 아니라면
  • 중간 노드 삭제 케이스
  • head = head.next
  • nodeCount -= 1
  • pos가 nodeCount 같다면,
    • 마지막 노드 삭제 케이스
    • prev.next = None
    • tail = prev
    • nodeCount -= 1
• 중복되는 코드 리팩토링

def popAt(self, pos):
        delete_node = self.getAt(pos)

        if pos < 1 or pos > self.nodeCount:     # pos가 1보다 작거나, 리스트의 길이보다 클때 IndexError 발생
            raise IndexError 

        if pos == 1:    # 첫 번째 노드 삭제 케이스
            if self.nodeCount == 1:    # 노드가 1밖에 없는 케이스
                self.head=None
                self.tail=None
                self.nodeCount = 0
            else:                          
                self.head = self.head.next
                self.nodeCount -= 1
            
            return delete_node.data
        else:                           # 중간 노드 삭제 케이스
            prev = self.getAt(pos - 1)
            prev.next = delete_node.next
            if pos == self.nodeCount:   # 마지막 노드 삭제 케이스
                prev.next = None
                self.tail = prev
                
        self.nodeCount -= 1
        return delete_node.data