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

illstandtall·2021년 4월 28일
0

Programmers dev course

목록 보기
3/34
post-thumbnail

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


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

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

연결리스트의 장점

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

연결리스트의 단점

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

연결리스트 vs 배열

배열연결리스트
저장공간연속한 위치임의의 위치
특정 원소 지칭매우 간편선형탐색과 유사
시간 복잡도O(1)O(1)O(N)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(1)
중간에 삽입하는 경우O(N)O(N)
맨 끝에 삽입하는 경우O(1)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(1)
중간에 삭제하는 경우O(N)O(N)
맨 끝에 삭제하는 경우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

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

profile
주니어

0개의 댓글