[자료구조] Array와 Linked List

Array

어레이는 어떤 언어에나 존재하는 가장 기본적인 자료구조로 고정된 크기의 연속된 메모리를 말한다.

 

순서대로 번호(인덱스)가 붙은 원소들이 연속적인 형태로 구성된 구조를 뜻하며 인덱스를 알면 해당원소에 접근할 수 있다.

 

원소들이 연속적으로 배치되어 있기때문에 인덱스로 원소에 접근할때 O(1)의 시간복잡도를 가진다.

 

배열은 참조형 타입으로 변수명 자체가 레퍼런스를 저장하고 있기때문에 변수자체를 포인터로 활용할수 있다.

이때 배열은 연속적인 위치를 보장하므로 (포인터값 + 데이터형의 크기)로 다음요소에 접근할수 있다.

 

한계점:

• 고정된 크기 
  • 배열 자료구조는 선언시에 할당된 메모리크기가 고정되어있기 때문에 배열의 크기를 늘려야 할때는 크기가 큰 새로운 배열을 생성하고, 기존 내용을 복사하거나 배열일부를 연결리스트 등으로 다른곳과 연결하는 등의 방법이 쓰인다.
  • 처음에 할당한 배열 크기만큼 배열공간을 사용하지 않을경우 사용되지 않은 메모리공간이 낭비되게 된다.
  • 연속된 메모리공간만을 할당받아야 하기때문에 메모리사용이 비효율적이다.( 흩어져있는 메모리를 모아서 사용할수 없기 때문 )

 

• 삽입과 삭제
  • 배열의 중간에서 삽입과 삭제시 삽입한원소 혹은 삭제한 원소보다 큰 값을 가지는 원소들은 모두 자리를 shift해줘야하는 비용이 발생하고 이경우 시간복잡도는 O(n)이 된다. 
  • 다만 가장 끝에 원소 추가 삭제의 경우 이동시킬 원소가 존재하지 않으므로 시간복잡도는 O(1)이다.

따라서 삽입과 삭제가 빈번한 상황에서는 배열을 쓰는것을 지양한다.

 

장점 :

• 인덱스만 알면 조회에 시간이 O(1)밖에 걸리지 않기 때문에 조회가 빈번한 상황에서는 배열을 사용하도록 한다.

배열은 언제 사용하면 좋을까?

• 데이터 개수가 확실하게 정해져 있을때 데이터저장을 위한 자료구조로 선택하면 좋다.
• 삽입/삭제가 적고 조회(검색)이 빈번할때

 

LinkedList

배열의 한계점을 극복하기 위해 만들어진 자료구조로 각 노드가 데이터와 포인터를 가지고 한줄로 연결된 방식으로 데이터를 저장하는 자료구조이다.

연결리스트 출처- 나무위키

 

장점 :

• 배열의 단점인 고정된 크기를 해결한점으로, 리스트의 길이가 가변적이다.
• 중간에서의 삽입/삭제도 O(1)시간에 가능하다. 위치만 알면 삽입/삭제시 앞뒤 포인터만 바꿔주면 되기때문에 그렇다.

 

단점 : 

• 임의의 노드에 바로접근이 불가능 : 순차접근만 가능하기 때문에 임의의 위치에 있는 원소를 찾는데 최악의 경우 O(n)시간이 걸린다. 
• 다음노드 위치를 저장하기위한 추가공간이 필요

 

한계점:

• 아이러니한것이 삽입/삭제가 O(1)에 가능하지만, 결국 어떤노드를 삽입/삭제 할것인지에 대한 탐색과정에서 O(n)이 걸린다는 것이다. Array와 달리 논리적저장순서와 물리적 저장순서가 일치하지 않기 때문이다.
• 즉 결국 검색에도 O(n), 삽입과 삭제에도 O(n)의 시간복잡도를 갖는다.

언제 연결리스트를 사용하는가?

• 연결리스트는 Tree자료구조의 근간이 되는 자료구조로, tree에서 진가를 발휘한다.

연결리스트의 구현 by Python

# LinkedList 구현 210711

class Node(object):
    def __init__(self, data, next=None):
        self.data = data
        self.next = next


class SingleList(object):
    def __init__(self):
        self.head = Node(None)
        self.size = 0

    def listSize(self):
        return self.size

    def is_empty(self):
        if self.size != 0:
            return False
        else:
            return True

    def selectNode(self, idx):
        if idx >= self.size:
            print("Index Error")
            return None
        if idx == 0:
            return self.head
        else:
            target = self.head
            for cnt in range(idx):
                target = target.next
            return target

    # 맨 왼쪽에 추가 head를 변경
    def appendLeft(self, value):
        # 연결리스트의 원소가 하나도없는경우 헤드만 추가되는 노드를 가리키도록
        if self.is_empty():
            self.head = Node(value)
        else:
            # 헤드가 가리키던 화살표를 추가되는 노드가 가지는 화살표로 바꿔준다.
            self.head = Node(value, self.head)
        self.size += 1

    # 맨 오른쪽에 추가
    def append(self, value):
        if self.is_empty():
            self.head = Node(value)
            self.size += 1
        else:
            # 현재의 헤드다음 노드 -> 맨마지막 노드를 향해 간다.
            target = self.head
            while target.next != None:
                target = target.next
            # 맨 마지막에 추가될 노드이므로 두번째인자는 주지않는다. -> None으로 초기화
            newTail = Node(value)
            target.next = newTail
            self.size += 1

    #idx에 새로운노드 추가 ->
    # idx이전노드의 next가 가리키던 값을 자신의 next로
    # idx이전노드의 next는 자신으로
    def insert(self, value, idx):
        if self.is_empty():
            self.head = Node(value)
            self.size += 1
        else:
            target = self.selectNode(idx-1)
            newNode = Node(value)
            newNode.next = target.next
            target.next = newNode
            self.size += 1

    def delete(self, idx):
        if self.is_empty():
            print("삭제할 노드가 없다.")
            return
        elif idx>= self.size:
            print("인덱스에러")
            return
        elif idx == 0:
            target = self.head
            self.head = target.next
            del(target)
            self.size -=1
        else:
            target = self.selectNode(idx-1)
            deltarget = target.next
            target.next = deltarget.next
            del(deltarget)
            self.size -=1

    def printlist(self):
        target = self.head
        while target:
            if target.next != None:
                print(target.data, '->', end=" ")
                target = target.next
            else:
                print(target.data)
                target = target.next # None


mylist = SingleList()
mylist.append('A')
mylist.printlist()
mylist.append('B')
mylist.printlist()
mylist.append('C')
mylist.printlist()
mylist.insert('D', 1)
mylist.printlist()
mylist.appendLeft('E')
mylist.printlist()
print(mylist.listSize())
mylist.delete(0)
mylist.printlist()
mylist.delete(3)
mylist.printlist()
mylist.delete(0)
mylist.printlist()
mylist.appendLeft('A')
mylist.printlist()

# A
# A -> B
# A -> B -> C
# A -> D -> B -> C
# E -> A -> D -> B -> C
# 5
# A -> D -> B -> C
# A -> D -> B
# D -> B
# A -> D -> B