7강/8강: 연결 리스트(Linked Lists) (1)/(2)

강의

"연결 리스트"는 선형 배열과 비슷한 구조입니다.

	배열	연결 리스트
저장공간	연속한 위치	임의의 위치
특정 원소 지칭	매우 간편	선형탐색과 유사
시간 복잡도	O(1)	O(n)

 

 

연결 리스트의 Node는 Data와 Link(next)로 이루어져 있습니다.

머리 부분을 Head, 마지막을 Tail이라고 부릅니다.

nodeCount를 이용하여 노드의 개수를 지정하면 유용합니다.

 

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

 

연결 리스트에서의 연산

1. 특정 원소 참조 (k 번째) : head = 1

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

2. 리스트 순회하기

3. 길이 얻어내기

4. 원소 삽입하기

 

 

 

 

 

 

⭐ 코너 케이스 주의!

• 삽입하려는 위치가 맨 앞일 때
• 삽입하려는 위치가 맨 끝일 때

def insertAt(self, pos, newNode):
	# 1 <= pos <= nodeCount+1
    
    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

5. 원소 삭제하기

⭐ 코너 케이스 주의!

• 제거하려는 위치가 맨 앞일 때
• 제거하려는 위치가 맨 끝일 때

 

6. 두 리스트 합치기

def concat(self, L):
	self.tail.next = L.head
    
    if L.tail:	#L.tail 유효한 경우
    	self.tail = L.tail
    self.nodeCount += L.nodeCount

 

 

7강 실습: 연결 리스트 순회 구현하기

⭐ 리스트를 순회하며 출력할 리스트에 저장하는 문제!

def traverse(self): 
    trav = []

    i = 1
    curr = self.head

    while i <= self.nodeCount:
        trav.append(curr.data)

        curr = curr.next
        i += 1

    return trav

 

 

8강 실습: 연결 리스트 노드 삭제하기

⭐ 코너 케이스에 주의하며 구현하는 문제!

⭐ raise Error 주의!

def popAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            raise IndexError
        
        curr = self.getAt(pos)
        
        if self.nodeCount == 1:
            self.nodeCount = 0
            self.head = None
            self.tail = None
        
        else:             
            if pos == 1:
                self.head = curr.next
            
            else:
                prev = self.getAt(pos-1)
                
                if pos == self.nodeCount:
                    self.tail = prev
                    prev.next = None    #tail.next 초기화
            
                else:
                    prev.next = curr.next

            self.nodeCount -= 1
        
        return curr.data