[자료 구조] 배열 & 연결 리스트 (Array & LinkedList)

Hailey Park·2022년 2월 10일

자료구조

목록 보기

1/2

배열 (Array)

배열은 입력된 데이터들이 메모리 공간에서 연속적으로 저장되어 있는 자료구조이다.
메모리 상에서 연속적으로 저장되어 있는 특징을 갖기 째문에, index를 통한 접근이 용이하다.
배열의 크기는 처음 생성할 때 정하며 이후에는 변경할 수 없다.

시간 복잡도

탐색 : O(1). 단, 접근하고자 하는 인덱스를 알고 있어야 한다. 순차적으로 탐색시에는 O(n).
삽입 / 삭제 :
- 배열의 처음 또는 중간에 삽입 및 삭제 : O(n)
  (삽입 지점 이후의 데이터를 옮겨야 하기 때문.)
- 배열의 끝에 삽입 및 삭제 : O(1)

연결 리스트 (Linked List)

연결 리스트는 여러 개의 노드들이 순차적으로 연결된 형태를 갖는 자료구조이며, 첫번째 노드를 head, 마지막 노드를 tail이라고 한다.
각 노드는 데이터와 다음 노드를 가리키는 포인터로 이루어져 있다.
배열과는 다르게 메모리를 연속적으로 사용하지 않는다.
배열과는 다르게 순차적으로 접근해야 하는 면에서 불리할 수도 있으나, 노드가 연결된 구조이기 때문에 삽입, 삭제에 용이하다.
Tree 구조의 근간이 되는 자료구조이며, Tree 에서 사용되었을 때 그 유용성이 드러난다.

시간 복잡도

탐색 : O(n)
삽입 / 삭제: 삽입과 삭제 자체는 O(1)이다.
- 연결 리스트의 처음에 삽입/삭제 : O(1)
- 연결 리스트의 중간에 삽입/삭제 : O(n) (탐색시간 소요)
- 연결 리스트의 끝에 삽입/삭제 :
  - 끝을 가리키는 별도의 포인터를 갖는 경우 : O(1)
  - 끝을 가리키는 별도의 포인터를 갖지 않는 경우 : O(n) (탐색시간 소요)

배열과 연결 리스트 비교

장점

배열 : 인덱스를 통한 빠른 접근 가능
연결 리스트 : 삽입/삭제 용이

단점

배열 :
- 삽입/삭제가 오래 걸림
- 배열 중간에 있는 데이터가 삭제되면, 공간 낭비가 발생함
연결 리스트 : 임의 접근이 불가능하여, 처음부터 탐색을 진행해야 함

용도

배열 : 빠른 접근이 요구되고, 데이터의 삽입과 삭제가 적을 때
연결 리스트 : 삽입과 삭제 연산이 잦고, 검색 빈도가 적을 때

연결 리스트 순회/삽입/삭제 코드 구현

프로그래머스 어서와! 자료구조와 알고리즘은 처음이지? 강의 실습 예제 (파이썬)

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


    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


    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


    def popAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            raise IndexError
            
        node = self.getAt(pos)

        if self.nodeCount == 1 & pos == 1: 
            self.head = None
            self.tail = None

        elif pos == 1:
                self.head = self.getAt(pos+1)

        else:
            prev = self.getAt(pos-1)
            
            if pos == self.nodeCount:
                prev.next = None
                self.tail = prev

            else:
                prev.next = prev.next.next

        self.nodeCount -= 1
        return node.data

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

이중 연결 리스트 (Doubly Linked List)

이중 연결 리스트는 위에서 언급한 연결 리스트와 다르게 전/후로 탐색이 가능한 구조이다.
즉, 단순 연결 리스트의 노드는 데이터와 다음 노드의 주소를 저장한다면, 이중 연결 리스트의 노드는 데이터, 이전 노드의 주소와 다음 노드의 주소를 저장하게 된다.
장점 : 단순 연결 리스트에서는 최악의 경우 n번의 탐색을 해야하지만, 이중 연결 리스트에서는 얻고자 하는 데이터의 위치가 tail에 가깝다면 tail에서부터 역방향으로 탐색이 가능하기 때문에 탐색 시간을 줄일 수 있다.