[자료구조] 연결리스트 (링크드 리스트), array vs linked list

어레이 vs. 연결리스트

Array는 애초에 공간을 이미 다 만든다! 나 n 개 만들거야 ➡️ 메모리에 주소 n개 할당함. 바뀔 수 없음

만약 메모리를 더 넣고싶으면(ex. 그림에서는 10번째부터, 메모리를 더 할당하여 넣는다.)

n번째 데이터가 보고싶다면 굳이 하나씩 체크할 필요 없이, A[n]으로 바로 확인 가능하다.

Linked List는 4번째에 접근하고 싶다면 바로 갈 수 없다. 0번째 > 1번째 > ... > 4번째로 가야한다.

• 어레이: 접근 쉬움, 삽입 어려움.
• 연결리스트: 직접 구현. 접근 어려움, 삽입 쉬움.

 

💡 파이썬에서 리스트는 Java의 ArrayList 와 매우 유사한 동적 배열(dynamically resizable array)의 개념을 기반으로 구현되어 있습니다.

동적 배열은 기본적으로 배열의 크기가 자동으로 조절될 수 있는 데이터 구조입니다. 배열의 크기를 고정하지 않고 필요에 따라 크기를 늘리거나 줄일 수 있습니다.
즉, 내부적으로 배열과 유사하게 연속적인 메모리 블록을 사용하지만, 크기를 자동으로 조절할 수 있는 특성을 가지고 있습니다.

링크드 리스트(linked list)와는 달리, 인덱스를 사용하여 요소에 직접 접근할 수 있으며, 이 접근이 평균적으로 O(1)의 시간 복잡도를 가집니다.

반면에 링크드 리스트는 각 요소가 이전과 다음 요소에 대한 참조를 가지고 있어, 요소에 접근할 때 O(n)의 시간 복잡도를 가지며, 삽입이나 삭제는 O(1) 시간에 수행할 수 있습니다.

---

클래스

코드 모아둔 것.

class Person:
    def __init__(self, name):
        self.name = name

    def sayhello(self, to):
        print(f"hello {to}, I'm {self.name}")


rtan = Person("rtanny")
rtan.sayhello("hanghae")

---

연결리스트의 구현

structure.py

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)

 

 

팰린드롬 연결 리스트

Given the head of a singly linked list, return true if it is a palindrome or false otherwise.

Pailndrome: 앞에서부터 읽으나 뒤에서부터 읽으나 동일한 단어 혹은 구
ex. racecar, tacocat

https://leetcode.com/problems/palindrome-linked-list/description/

 

test.py

from linkedlist.prac import isPalindrome
from linkedlist.structures import LinkedList

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

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

assert isPalindrome(l1.head)
assert not isPalindrome(l2.head)

 

prac.py

def isPalindrome(head):
    arr = []

	# 빈 링크드 리스트 일 경우는 그냥 True 반환
    if not head:
        return True

    node = head
    while node:
        arr.append(node.val)
        node = node.next

    while len(arr) > 1:
    	# 하나라도 다를 경우엔 False
        if arr.pop(0) != arr.pop():
            return False
	# 모두 통과 하면 True
    return True