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

배열(Array)

배열이란?

• 동일한 데이터 타입의 요소들을 연속된 메모리 공간에 순서대로 저장하는 자료구조
• 데이터 조회에서 O(1)의 [[시간 복잡도]]를 가진다.

장점

• 연속된 메모리 공간을 사용하므로 처음 데이터의 주소를 알면 나머지도 쉽게 찾을 수 있다.

단점

• 크기가 고정되어 추가/삭제에 제약이 있다.

연결리스트 (Linked List)

연결리스트란?

• 각각의 데이터가 메모리 공간 상에 고유한 노드로 존재하며, 해당 노드에 앞과 뒤의 메모리 주소를 기억하고 있는 형태
• 즉, 노드들이 서로 연결되어 있는 구조
• 데이터 조회 시 순차적으로 탐색하기 때문에 O(N)의 시간 복잡도
• 데이터 추가와 삭제에는 O(1)의 시간 복잡도

Array vs Linked List

• 배열 (Array): 파이썬의 리스트. 접근 쉬움, 삽입 어려움. (파이썬의 리스트)
• 연결리스트: 직접 구현. 접근 어려움, 삽입 쉬움.
  상자랑 화살표 포함해서 노드라고 함

구현

# structures.py

'''
O -> O -> O -> O -> O -> O -> O 형태이다.
''' 
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val # 상자
        self.next = next # 화살표


class LinkedList:
    def __init__(self):
        self.head = None # 제일 첫 요소

    def append(self, val):
        if not self.head: # 헤드가 없다면
            self.head = ListNode(val, None) # 헤드 노드를 하나 만들고 다음거는 없다
            return

        node = self.head # 제일 앞을 노드로 설정
        while node.next: # 다음 요소가 있을 동안 (없을 때 까지)
            node = node.next # 노드를 다음걸로 업데이트

        node.next = ListNode(val, None) # 다음 요소 없으면 새로 만들기!

예제

Q.
주어진 리스트가 팰린드롬인지 판별하는 프로그램을 작성하세요.
(팰린드롬 : 읽는 순서가 바뀌어도 똑같은 것)

예시1) [1, 2, 2, 1] ⇒ True
예시2) [1, 2] ⇒ FalseContent

isPalindrome : 팰린드롬인지 확인하는 함수는 어떻게 만들까?

1. 연결리스트를 리스트로 만든 후,
2. 리스트의 첫 번째 요소와 마지막 요소를 꺼내서 같은 지를 확인한다.

👇

#prac.py

def isPalindrome(ln): # 연결리스트를 전달받아서
    arr = []
    head = ln.head #헤드를 꺼내 

    if not head: #헤드가 없으면 비어있으므로
        return True

    # 헤드가 있으면
    node = head
    while node: # 노드를 옮겨가며 연결리스트의 모든 값을 리스트에 넣는다.
        arr.append(node.val)
        node = node.next

    while len(arr) > 1: # 길이가 1이 될 때 까지
        # 첫 번째 요소와 마지막 요소를 꺼낸다.
        first = arr.pop(0)
        last = arr.pop()
        if first != last: # 다르면 팰린드롬이 아님
            return False

    return True

위에서 만든 팰린드롬 검사 함수를 test.py에서 사용하기

# test.py

from structures import LinkedList
from prac import isPalindrome

l1 = LinkedList() # 1->2->2->1
for num in [1, 2, 2, 1]:
    l1.append(num)

l2 = LinkedList()
for num in [1, 2]:
    l2.append(num)


assert isPalindrome(l1) # assert 뒤의 값을 true로 확언하겠다 (true가 맞는지 test하는 것)
assert not isPalindrome(l2) # assert not 뒤의 값을 false로 확언하겠다 (false 가 맞는지 test하는 것)