자료구조 (1) - Array, Linked List

자료구조 (1) - Array, Linked List

해당 글에서는 기본적인 자료구조인 Array. Linked_List를 정리하려고 한다.

사실 실제 기본적인것은 느낌만 있을뿐 처음 배웠던 자료구조이기 때문이다.

< 개념 >

우선 둘다 리스트의 형태를 띈다. 여기서 리스트의 형태는

다음과 같은 체크 리스트 처럼

당근

파

댤걀 10개

오리온 초코파이

예감

...

데이터들을 정렬하는 방법이다.

<차이점>

Array와 Linked List 둘다 데어티가 정렬된 형태를 띄지만 저장 방식이 다름

Array, Linked List의 저장 방식

Array는 연속된 순서대로 값이 저장되기 때문에 데이터의 index가 존재하고 공간이 정해져 있다. 공간이 정해져 있기 때문에 너무 큰 사이즈의 경우 다른 자원을 침범할 수 도 있기 때문에 저장공간에 제약이 생김

하지만 Linked List는 이와는 별개로 Index가 존재하지 않고 앞을 의미하는 Head, Tail, 각 데이터들의 다음이 누구인지만 가르키고 있기 때문에 공간의 제약이 전혀 없다. 각각의 데이터들은 서로 무작위의 위치에 저장이 되기 때문이다.

<구현>

Array의 구현은 단순히 Python 내부함수인 List를 사용하면 된다

a = [1, 2, 3, 4]

Linked List의 구현은 내부함수가 따로 존재하지 않아서 Class로 정의를 해야하며 다음과 같다

class Node: def __init__(self, data): # data를 담을 Node Class부터 정의 self.data = data # data : 저장될 데이터 self.next = None # next : 다음 노드를 가리키는 class LinkedList: # Linked List Class def __init__(self, value): self.head = Node(value) # head : Linked LIst의 처음 노드임을 알려줌 def append(self, value): # apppend : 노드를 추가하는 함수 cur = self.head while cur.next is not None: cur = cur.next cur.next = Node(value) def get_all_data(self): # get_all_data : 현재 리스트에 있는 데이터를 순서대로 모두 출력 stringbox = '' curr = self.head while curr.next is not None: stringbox += str(curr.data) curr = curr.next stringbox += str(curr.data) return int(stringbox)

끝을 정의하는 tail은 해당 예시에서 구현하지 않았지만 지정할 수 있으며 경우에 따라서 Oneway Linked List가 아니라 양방향으로 이동하는 Class로 변경할 수 있다.

그리고 Linked List는 이후에 배울 Queue 같은 다른 자료구조를 만들때도 이용할 수 있다.

이를 활용한 내용으로는 핸드폰에 있는 지금까지 사용한 앱 확인할 때 나오는거 등등 많은 곳에서 사용된다.

링크드 슬라이드 예시

from http://zhqmfkv.tistory.com/30 by ccl(A) rewrite - 2021-12-17 14:27:20