배열

노타빌리티에서 직접 그려본 하찮고 귀여운 내 그림...

특징

• python에서 '리스트' 라는 추상적 자료형을 구현한 대표적인 예시
• 배열에 저장되는 값들은 순서를 나타내는 번호(인덱스)를 가진다.
• 같은 종류의 데이터를 효율적으로 관리해야 하는 경우에 사용

구현

mylist = [1, 2, 3, 4, 5]

# 조회
print(mylist[0]) # 1

# 삽입
mylist.append(6) # [1, 2, 3, 4, 5, 6] - 맨 뒤에 원소 삽입
mylist.insert(3, 10) # [1, 2, 3, 10 , 4, 5, 6] - 특정 인덱스에 원소 삽입

# 삭제
del mylist[3] # [1, 2, 3, 4, 5, 6] - 인덱스로 삭제
mylist.remove(6) # [1, 2, 3, 4, 5] - 값으로 삭제
mylist.pop() # [1, 2, 3, 4] - 매개변수 입력 않을 시 맨 마지막 값(-1) 삭제

⭕️ 장점

• 배열 내의 특정 값을 조회할때 간편하다.

❌ 단점

• 자료의 삽입/삭제가 번거롭다.

연결 리스트 (링크드 리스트)

특징

• python에서 '리스트' 라는 추상적 자료형을 구현한 또 다른 예시
• 여러 개의 '노드'를 저장하는 방식으로 구현한다. 각 노드는 자신의 다음 순서의 노드를 가리킨다.
• 노드는 저장하는 값 자체를 의미하는 '자료'와 다음 노드를 가리키는 '포인터'로 구성되어 있다.

구현

# 노드 구현
class Node:
	def __init__(self, data, next):
    	self.data = data
        self.next = next

node1 = Node("hi")
node2 = Node(1120)
node3 = Node("merong")

# 노드 연결
node1.next = node2
node2.next = node3

# 링크드리스트 구현
class LinkedList:
    def __init__(self) :
        self.start = None # 시작 정점
        self.end = None # 끝 정점
        # 연결리스트에 아무런 정점도 들어있지 않은 상태. 배열에서 myList=[]와 같은 의미
    
    
    ### 조회
    def getNode(self, pos): # pos에 위치하는 노드 조회
        if pos < 0:  
            return None  
        node = self.start
        # 시작 정점부터 순차적으로 보기 위해 시작 정점을 넣어줌
        while pos > 0 and node != None:  
        # pos가 0보다 크고 node가 존재할 경우에 반복
            node = node.next  
            # 시작 정점부터 순차적으로 검사
            pos -= 1
        # pos = 0이 되면 해당값에 도달. 
        return node  # 해당값 return
        
    def getList(self) : # 링크드리스트를 배열로 return
        result = []
        current = self.start
        while current != None:
            result.append(current.data)
            current = current.Next
        return result


    ### 삽입
    def addFront(self, data) : # 맨 앞에 삽입
        ### 연결리스트가 비어있는 경우
        if self.start == None and self.end == None:
            elem = Node(data, None) 
            # 다음값이 없기에 포인터는 None
            self.start = elem
            self.end = elem
            # 첫번째 값이기 때문에 시작 정점과 끝 정점은 동시에 elem이 들어감
            
        ### 연결리스트가 비어있지 않은 경우
        ### 왼쪽으로 삽입되는 경우, 삽입되는 값이 새로운 시작 정점이 된다.
        else:
            elem = Node(data, self.start) 
            # 따라서 다음 값을 가리키는 포인터에는 self.start를 넣는다.
            self.start = elem
            # 시작 정점을 새로운 값이 차지

    def addBack(self, data) : # 맨 뒤에 삽입
        ### 비어있는 경우 (addLeft와 동일)
        if self.start == None and self.end == None:
            elem = Node(data, None)
            self.start = elem
            self.end = elem
            
        ### 비어있지 않은 경우
        ### 오른쪽으로 삽입되는 경우, 제일 끝에 들어가므로 다음값은 존재하지 않음
        else:
            elem = Node(data, None) 
            # 따라서 다음 값을 가리키는 포인터는 None
            self.end.Next = elem
            # 기존 끝 정점의 next에 elem 넣어주기
            self.end = elem
            #링크드리스트의 마지막을 새로운 값이 차지
            
    def addNode(self, pos, data):  # 원하는 위치(pos)에 삽입
        prev = self.getNode(pos - 1) # 추가하려는 위치 바로 앞의 노드
        if prev == None: 
        # 맨 앞에 추가하는 경우
            self.start = Node(data, self.start)  
            # 현재 값이 시작 정점 차지. (next값은 원래 시작 정점)
        else:
            node = Node(data, prev.next)  
            # '기존 prev의 다음 위치를 가리키는 포인터'를 가진 노드 추가
            prev.next = node  
            # prev의 next는 node(추가한 노드)를 가리키도록 한다.
    
    
    ### 삭제
    def deleteNode(self, dataToDelete):
        node = self.start
        start = node
        prev = None # 시작 정점부터 보기 때문에 이전 값은 아직 None
        while node: # 시작 정점부터 순차적으로 반복문 시작
            if node.data == dataToDelete: 
            # Node의 값이 지우려는 값일 때
                if prev == None: 
                # 지우려는 Node가 시작정점이여서 앞에 아무것도 없을 때
                    self.start = node.next 
                    # 본인만 지우니 다음 값이 시작 정점이 된다.
                else: 
                # 지우려는 Node가 시작정점이 아닐 때 (=앞에 prev가 있을 때)
                # 앞, 뒤 연결해주고, 사이 연결 끊기
                    prev.next = node.next 
                    # 이전 노드와 현재값의 다음 노드 연결(앞-뒤 연결)
                    if prev.next == None:
                    # 이전 노드의 다음 값이 없다면 (=이전 노드가 끝 정점이 되었다면)
                        self.end = prev 
                        # prev를 끝 정점으로 지정
            prev = node 
            node = node.next # prev, node를 각각 다음 값으로 넘겨서 계속 반복
        return start

⭕️ 장점

• 자료의 삽입/삭제가 간편하다.

❌ 단점

• 특정 위치의 자료를 조회할 때 번거롭다.
  (배열은 찾는 자료의 위치와 관계없이 항상 단번에 값을 찾을 수 있지만, 링크드 리스트는 찾는 자료의 위치가 시작점으로부터 멀수록 연산 횟수가 많아진다.)

배열과 링크드 리스트의 차이

배열: 순차적으로 연결된 공간에 데이터를 나열하는 구조
링크드 리스트: 각각 떨어져 있는 별도의 데이터들을 임의로 연결하는 구조
-> 전체 요소를 순회하는 연산 또한 메모리 특성 상 배열이 더 유리하다.