1. 알고리즘 공부 배열, 리스트 (파이썬 네이티브 코드로 구현하기)

1. Array (배열)

• 배열은 크기가 정해진 데이터의 공간. 한 번 정해지면 바꿀 수 없다.
• 배열은 각 원소에 즉시 접근할 수 있다. 
• 여기서, 원소의 순서는 0부터 시작하고 이를 인덱스라 부른다.
• 배열은 원소를 중간에 삽입/삭제 하려면 모든 원소를 다 옮겨야 한다.
• 원소를 새로 추가하려면, 새로운 공간을 할당해야 하므로 매우 비효율적인 자료구조.

2. Linked List(링크드 리스트) 혹은 리스트(List)

• 리스트는 크기가 정해지지 않은 데이터의 공간
• 리스트는 특정 원소에 접근하려면 오래 걸린다.
• 리스트는 원소를 중간에 삽입/삭제 하기 위해서 앞 뒤의 포인터만 변경하면 된다. 즉 원소 삽입/삭제가 간단하다.

배열과 리스트의 차이

배열 : 배열의 끝에서만 추가/삭제 연산을 하거나 추가/삭제 연산이 없는 경우 사용

리스트 : 추가/삭제 연산이 많이 필요한 경우 사용 

	Array	List
특정 원소 조회	빠름	느림
중간에 삽입 삭제	느림	빠름
데이터 추가	새로운 메모리 공간을 할당 받아야함	능동적으로 축 ㅏ가능
정리	데이터에 접근하는 경우가 빈번할 때 사용	삽입과 삭제가 빈번하다면 사용

파이썬의 list는 array로 구현되어 있다.
파이썬은 내부적으로 동적 배열이라는 걸 사용해서, 배열의 길이가 늘어나도 시간이 오래걸리지 않게 설계했다.

우리가 알아야 할 건 파이썬의 배열은 리스트로 쓸 수도 있고
배열로도 쓸 수 있게 만든 효율적인 자료구조라는 사실

 

3. 리스트 네이티브 코드 구현

리스트의 노드는 두가지 정보가 필요하다

1. 칸에 있는 데이터
2. 다음 칸이 뭔지

class Node:
	def __init__(self, data):
    	self.data = data
        self.next = None
        
# 3을 가진 Node를 만드려면 아래와 같이 하면 된다
node = Node(3) #현재는 next가 없이 하나의 노드만 있다

클래스의 생성자에 data를 인자로 받아 self.data에 저장한다.

그 후 현재는 다음 이어진 노드가 없기 때문에 self.next에는 None을 넣어두면 된다

first_node = Node(5) # 현재는 next가 없어 하나의 노드만 있다. [5]
second_node = Node(12) #[12]를 들고 있는 노드를 만든다.
first_node.next = second_node # 그리고, [5]의 next를 [12]로 지정한다.

위의 코드는 노드들을 만들어 연결하는 과정이다.

 

이 노드들을 하나하나 계속 연결해준다면 너무 번거롭다. 따라서 LinkedList라는 클래스를 만들어보자.

1. LinkedList 는 self.head 에 시작하는 노드를 저장한다.
2. 다음 노드를 보기 위해서는 각 노드의 next를 조회해서 찾아가야 한다.

class LinkedList:
    def __init__(self, data): 
        self.head = Node(data) # head 에 시작하는 Node를 연결한다
        
linked_list = LinkedList(5)
print(linked_list.head.data) # 5가 출력된다!

# 현재 LinkedList 는 (5) 만 존재한다

이번엔 리스트의 맨 뒤에 새로운 Node를 붙이는 append함수를 만들어보자.

현재 있는 노드의 가장 맨 뒤에 새로운 값을 가진 노드를 추가하려면 맨 뒤의 노드까지 가야한다.

즉 head를 따라 가다가 마지막에 next에 None값이 있으면 그 위치가 마지막 노드다.

class LinkedList:
    def __init__(self, data):
        self.head = Node(data)  # head 에 시작하는 Node 를 연결.

    def append(self, data):
        if self.head is None:  #만약 시작이 없다면 새로운 Node를 만들어줌
            self.head = Node(data)
            return

        cur = self.head

        while cur.next is not None: #마지막 노드를 찾기위한 과정
            cur = cur.next
        cur.next = Node(data)


linked_list = LinkedList(5)
linked_list.append(12)
# 이렇게 되면 5 -> 12 형태로 노드를 연결
linked_list.append(8)
# 이렇게 되면 5 -> 12 -> 8 형태로 노드를 연결

다음 코드는 리스트에 있는 모든 노드를 출력하는 메소드다

def print_all(self):
        cur = self.head
        while cur is not None:
            print(cur.data)
            cur = cur.next

리스트에서 index번째 원소를 반환하는 법

    def get_node(self, index):
        node = self.head
        count = 0
        while count < index:
            node = node.next
            count += 1
        return node

count가 입력받은 숫자 index까지 증가하면서 index값과 같아지면 그때의 node값을 반환한다.

 

아래 코드는 리스트에서 index번째 원소를 반환하는 방법

    def add_node(self, index, value):
        new_nodee = Node(value)

        if index == 0:
            new_nodee.next = self.head
            self.head = new_nodee
            return
        
        node = self.get_node(index -1)
        next_node = node.next
        node.next = new_nodee
        new_nodee.next = next_node

 

1. next_node라는 변수에 현재 노드와 연결된 노드를 저장,
2. 현재 노드의 다음 노드를 새로운 노드와 연결
3. 새로운 노드의 다음 노드를 이전에 저장해둔 노드에 연결
4. 예외처리로 0이 입력될 경우 맨 앞에다가 추가 

삭제 메소드 

    def delete_node(self, index):
        if index ==0:
            self.head = self.head.next
            return
        node = self.get_node(index - 1)
        node.next = node.next.next