[Programmers] 2. 기본 자료구조: 연결리스트(Linked List) (1): 연결리스트 기본

오류에 대한 지적이나 질문, 토의 환영합니다. 자유롭게 댓글 남겨주세요!.!

---

자료구조 2. 연결리스트 (Linked List)

• 데이터 원소들을 순서를 지어 늘어놓는다는 점에서 연결리스트는 선형배열 (Linear array) 과 비슷한 면이 있습니다.
• 선형 배열은 번호가 붙여진 칸에 원소를 채워 넣는 방식이고,
• 연결리스트는 각 원소들을 줄줄이 엮어서 관리하는 방식입니다.

연결리스트의 장점

• 원소들이 고리로 연결되어 있으므로, 가운데 원소 하나를 끊어서 삭제하거나, 가운데를 끊고 새로운 원소를 삽입하는 것이 선형배열보다 쉽습니다. (빠릅니다.)
• 원소의 삽입/삭제가 빈번히 일어나는 응용 문제에서는 연결 리스트가 많이 이용됩니다.

연결리스트의 단점

• 선형배열에 비해 메모리 공간을 많이 차지합니다.
• k 번째의 원소를 찾는 시간이 선형배열에 비해 느립니다.

연결리스트 vs 배열

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

Python에서 연결리스트 Class로 구현

• 초기 Class

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 번째 원소 참조

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. 리스트 순회

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

3. 길이 얻어내기

def getLength(self):
    return self.nodeCount

4. 원소 삽입

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

• 원소 삽입의 복잡도

맨 앞에 삽입하는 경우	$O(1)$
중간에 삽입하는 경우	$O(N)$
맨 끝에 삽입하는 경우	$O(1)$

5. 원소 삭제

def popAt(self, pos):
    if pos < 1 or self.nodeCount < pos:
        raise IndexError
    
    if pos == 1:
        res = self.head.data
        if self.nodeCount == 1:
            self.head = None
            self.tail = None
        else:
            self.head = self.head.next
    else:
        prev = self.getAt(pos - 1)
        curr = prev.next
        res = curr.data
        if pos == self.nodeCount:
            prev.next = None
            self.tail = prev
        else:
            prev.next = curr.next
            
    self.nodeCount -= 1
    
    return res

• 원소 삽입의 복잡도

맨 앞에 삭제하는 경우	$O(1)$
중간에 삭제하는 경우	$O(N)$
맨 끝에 삭제하는 경우	$O(N)$

6. 두 리스트 합치기

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

---

이 글은 프로그래머스 스쿨 인공지능 데브코스 과정에서 공부한 내용을 바탕으로 정리한 글입니다.