My Profile Photo

DongChanS's blog

수학과 학생의 개발일지

• on data structure, algorithm, array, linked list

파이썬 자료구조 (1) Linked List

아래 포스트는 Data Structure and Algorithmic Thinking with Python을 참고하여 작성되었습니다.

  • 포인터를 기준으로 연결된 Sequence
  • 마지막 포인터는 Null
  • 프로그램 도중에 size를 자유롭게 변경가능
  • 메모리를 낭비하지 않을 수 있음(하지만 pointer를 위한 메모리가 필요하긴함)


Linked List 기능들

  1. Insert
  2. Delete(pop)
  3. Delete List(리스트의 모든 원소들 제거)
  4. Count
  5. Find nth node from the end of the list

연결리스트의 장단점을 논하기 위해서는 우리가 잘 알고있는 배열이랑 비교를 해보는게 좋습니다.

1


Arrays Overview

배열 : 하나의 메모리 block -> entire array를 가리킴.

array element는 index를 통해서 constant time만에 값에 접근가능합니다.


Why Constant Time for Accessing Array Elements?

array의 원소에 접근하기 위해서, 각 원소의 주소는 base address + offset으로 계산할 수 있습니다.

offset = index * size of data type 이므로 각 원소의 주소를 계산하는데 곱셈 한번, 덧셈 한번만이 요구됩니다. 따라서 상수시간만에 접근이 가능합니다.


Array의 장단점

  • 장점

    쉽다, 각 원소에 접근하는 시간이 빠르다.

    배열의 access time은 spacial locality를 가진다

    (메모리의 인접한 블록들을 가지기 때문에 array의 원소들은 물리적으로 근처에 있음: 현대 CPU caching method에 큰 이점이 있다고 함.)

  • 단점

    사이즈가 고정된다.

    One block allocation : 배열 전체를 메모리공간에 저장해야하기 때문에 배열의 사이즈가 길다면 허용되는 메모리가 없을 수 있다.

    Complex position-based insertion : 특정 위치에 원소를 넣기 위해서는 shifting이 필요하다. 만약 시작점에 원소를 넣고싶다면 당연히 shift를 많이 해야하므로 비용이 더 많이 들 것이다.


Dynamic Array

동적 배열은 random access + variable-size를 가진 리스트 데이터구조이며, 이것 역시 데이터를 추가하고, 제거하는것이 허용됩니다.

동적 배열을 만드는 가장 간단한 방법은

  1. fixed size array를 만든다

  2. array가 가득차면 크기를 두배 증가시켜서 새로운 array를 만든다.

  3. array의 원소가 절반이 되면 array의 size를 절반으로 감소시킨다.

    이러한 동적배열들을 만드는 방식은 Stack, Queue, Hashing 챕터에서 접하게 될 것입니다.


Linked List의 장단점

  • 장점

    constant time만에 확장이 가능하다.

    array와는 달리 array copy와 reallocating이 없이도 사이즈를 확장할 수 있다.

  • 단점

    access time : O(n) (worst case)

    때때로 다루기가 어렵다 : 예를 들어서 마지막 원소가 제거되었다면, 마지막에서 두번째 원소(The last but one)의 pointer가 바뀌어야합니다. 즉, 마지막에서 두번째 원소의 레퍼런스를 참조해서 그녀석의 포인터를 NULL으로 바꿔야한다는 말입니다.


1. 단순연결리스트

Linked list는 여러개의 노드로 이루어져있으며, 각 노드는 next pointer(link)를 가지고 있습니다.

마지막 node의 link는 Null입니다.

4

Node 클래스

class Node:
    def __init__(self):
        self.data = None
        self.next = None
    def setData(self,data):
        self.data = data
    def getData(self):
        return self.data
    def setNext(self.next):
        self.next = next
    def getNext(self):
        return self.next
    def hasNext(self):
        return self.next != None


1. 원소들을 집어넣기

  • head 이전에 집어넣기, tail 뒤에 집어넣기, 아무데나 집어넣기

    (p 위치에 새로운 원소를 넣으면 새로운 원소의 위치가 p가 되게 하려고함.)

class Singly:
    def __init__(self):
        self.head = None
        self.length = 0
        # tail같은거 없음
    def insertAtBeginning(self,data):
        newNode = Node()
        newNode.setData(data)
        if self.length == 0:
            self.head = newNode
        else:
            newNode.setNext(self.head)
            self.head = newNode
        self.length += 1
    def insertAtEnd(self,data):
        newNode = Node()
        newNode.setData(data)
        current = self.head
        while(current.getNext()):
            current = current.getNext()
        current.setNext(newNode)
        self.length += 1
    def insertAtPos(self,pos,data):
        # pos는 인덱스를 뜻함(포인터 아님)
        if pos == 0:
            self.insertAtBeginning(data)
        elif pos == self.length:
            self.insertAtEnd(data)
        else:
        """
        1. 새 노드를 만든다
        2. pos위치에 대체될 노드를 찾기 위해서 head에서 position-1 만큼 이동해서
        바로 이전의 노드를 찾는다.
        3. 바로 이전의 노드의 next값을 새 노드로 바꾼다.
        4. 새 노드의 next값을 대체될 노드로 바꾼다.
        """
            newNode = Node()
            newNode.setData(data)
            current = self.head
            for _ in range(pos-1):
                current = current.getNext()
            current.setNext(newNode)
            newNode.setNext(current.getNext())
            self.length += 1

2. 원소들을 제거하기

  • 첫번째 원소제거, 마지막 원소제거, 중간의 원소를 제거
  • delete는 비슷하니 생략하도록 하겠습니다.

3. 연결리스트 전체를 제거하기

파이썬은 garbage-collected 즉, 어떤 변수도 가리키지 않게 된 메모리영역을 탐지하여 자동으로 해제하는 기능을 가지고 있기 때문에

def clear(self):
    self.head = None

이라는 간단한 로직으로 리스트를 없애버릴수있다.


2. 이중연결리스트

이중연결리스트는 각 노드가 양쪽 방향을 전부 가리킨다는 장점이 있지,

단점은 두개의 포인터를 사용하기 때문에 메모리 요구량이 많고, 노드 삽입이나 삭제 연산이 조금 더 많이 필요하다는 점이 있다(포인터를 많이 필요로 하므로).

뒤에서도 검색할 수 있으므로 뒤에 있는 원소에 대해서는 검색시간에 대해서 장점이 있겠지만 그것도 생각보다 크지는 않은듯하다!

그러한 장점을 유지하기 위해서는 마지막 노드를 가리키는 tail노드를 구축해야한다.


3. 원형연결리스트

1,2의 연결리스트는 마지막에 NULL을 가리키지만 원형리스트는 end가 없다. 따라서 순회하는데 좀 공을 들여야한다. 그렇다보니 아무래도 많이 쓰이지는 않는다고 함.

그렇다고 해도 head노드를 없애지는 않는데, 이래야 다루기가 편하다.

원형 연결 리스트는 스택이나 queue를 만들기 위해서 자주 쓰인다. (ex : Deque)

4. Unrolled Linked Lists

연결리스트의 단점인 검색시간을 줄이기 위해서 연결리스트에 약간의 변화를 주었다고 합니다.

연결리스트는 각 노드(block이라고 부름)에 여러 element를 저장하는 방식입니다.

각 block에는 원형연결리스트로 원소들을 저장하고 있습니다.

(보통 전체 원소가 n이라고 하면 각 블록당 sqrt(n)개(celling function) 의 원소를 저장함)

2

이 리스트는 k번째 원소를 O(sqrt(n))만에 찾을 수 있다는 장점이 있습니다.

  1. k번째 원소는 k/sqrt(n) 블록만에 있음 -> 길어봐야 O(sqrt(n))
  2. 거기서 많아봐야 sqrt(n)개의 원소를 탐색함 -> O(sqrt(n))

그런데 당연히 단점도 존재하는데, 각 블록마다 sqrt(n)개의 원소밖에 못 집어넣으므로, 만약 블록에 원소가 가득차면 원소를 넣기 위해서 shift 연산을 적용해야합니다.

3

  1. 해당하는 블록에 원소를 넣는다
  2. 각 블록마다 뒤에 삐져나온 원소를 next 블록의 head에 넣는다.

그래서 원소를 넣는데도 길어도 sqrt(n)이내의 연산이 필요합니다.

  • 장점

    검색시간이 빠르다.

    메모리를 효율적으로 사용할 수 있음(sqrt(n)개의 메모리를 잘게 저장하면 되므로)

5. Skip Lists

이진트리(binary tree)는 원소들이 랜덤하게 저장되어 있을 때 좋은 성능을 발휘합니다(따라서 원소들이 제 순서를 가지고 있을 때는 성능이 별로 좋지 않음)

그러나 일반적으로는 데이터가 규칙을 갖는 경우가 대부분이기 때문에 이진트리는 실용적이지 않는데요, 그 대안으로 Balanced tree algorithm이 있습니다. (tree를 재배열하는 연산을 가지고있음)

Skip List는 balanced binary tree의 대안으로 사용된다는데.. 일단 트리를 몰라서 다음에 적도록 하겠습니다.

comments powered by Disqus