200105 TIL

Linked List

떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조

필요할 때마다 데이터를 추가하기 용이함. (기존의 배열은 다 짜놓고 하기 때문에 데이터를 추가하기 어려운 단점이 존재함)

• Node: 데이터 저장 단위(데이터값, 포인터)로 구성됨
• Pointer: 각 노드 안에서 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간

class Node:
  def __init__(self, data, next = None):
  self.data = data
  self.next = next

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

배열은 미리 확보한 공간에 빈 공간 없이 데이터를 저장해야 하는데, 링크드 리스트의 경우 이러한 단점을 해결하게 위해 생성됨

데이터를 추가하고 싶다면, 노드를 만들어서 연결만 해주면 되기 때문!

링크드리스트 이용

하나의 노드에는, 데이터와 주소를 저장해야 하는데, 이렇게 두 개를 저장하려면 클래스를 이용하는 것이 편리하다.

링크드리스트의 장단점

• 장점: 미리 데이터 공간을 할당하지 않아도 됨

• 단점: 연결을 위한 데이터 공간이 별도로 필요함, 연결 정보를 찾는 시간이 필요함, 중간의 데이터 삽입 또는 삭제시 연결을 재구성해야 함

(단점이 굉장히 많지만.. 정해진 공간 할당이 어려운 경우가 있기 때문에 사용되는 경우가 분명 있다)

간단한 링크드리스트 구현

 
class NodeMgmt:
  def __init__(self, data):
  self.head = Node(data)
  
  def add(self, data):
    if self.head == "":
      self.head = Node(data)
    else:
      node = self.head
      while node.next: # next 가 None 이 아니면
        node = node.next
      node.next = Node(data)
      
  def desc(self):
    node = self.head
    while node:
      print(node.data)
      node = node.next

맨날 까먹는 내용 T.T

• join 함수: Python을 사용할 때, join()을 사용하여 리스트의 요소들을 붙여 문자열로 출력할 수 있다.

  print(" ".join(list))
  

• 리스트 거꾸로 출력: 리스트나 문자열을 거꾸로 출력하고 싶을 때는, [::-1]와 같이 사용하면 거꾸로 출력할 수 있다.

  list.append(cmd[j][::-1])