Linked List

확실한 내용이 많지 않음을 미리 고지합니다.

Linked List

사실 이게 뭐다~ 정도만 알지 정확히 코드가 어떤 것을 의미하는지까지는 모르겠다. 링크드 리스트에 대한 다양한 자료들이 존재했고 이를 보고 이해한데로 정리한 뒤 추후 다시 리버스 링크드 리스트를 풀어보는 것이 좋을 것 같다. 아직은 이를 완전히 이해하고 하긴 무리다.

1. Linked List란??

설명 참고 블로그

• 우리가 밥집을 가서 줄을 서면 내가 몇 번째인지 앞사람과 관계를 통해서 알 수 있다. 이 때 중간에 사람이 하나씩 빠지거나(도저히 못 기다려서) 아니면 앞사람 순서가 되어서 하나씩 빠져 자리가 이동하는 경우 '순차적'으로 확인할 수 있다. 하지만 굳이 순차적으로 확인하지 않고 내 앞 뒤사람에 대한 번호표를 서로 가지고 있으면 어떻게 될까?

• linked list는 대기표처럼 자신의 앞, 뒤에 있는 데이터의 위치를 알 수 있는 번호표(포인터)가 있는 자료구조다. 여기서 대기하는 사람 한 사람 한 사람을 '노드'라고 하고 주로 클래스로 구현된다.
  

2. 단순한 배열과의 차이?

• 순차적 저장하는가? : 이에 따라 연결 링크를 따라 접근해야 하는 수고스러움이 있는가?
• 단 입력은 순차적으로 된다는 공통점은 있다.
• 근데 왜 쓰는가? : linked list는 조금 더 데이터 삽입이 유연하기 때문. 예를 들어 식당 줄을 섰을 때 번호표로 서로의 위치를 알고 있으면 중간에 끼어들어 추가 되더라도(물론 실제로 그러면 좀 열받겠지만) 순서를 그대로 알 수 있고 흩어져 있어도 충분히 찾기 편하기 떄문.
• 어레이보다 링크드 리스트가 더 많은 메모리를 차지한다. 노드 별로 객체를 생성해야 하니까.
  (이건 메모리 관련한 내용이라 잘 와닿진 않는다. 아마 일반 배열에서 일렬로 메모리를 차지하는 것과 달리 여러군데에 노드별로 객체를 만들어서 메모리 공간을 차지해서 그런가..? 이건 확실치 않다.)

3. 문제(리트코드 707번)

• get(index) : linked list 의 index 번째 node의 value를 return해주세요. 값이 없으면 -1을 return해주세요.
• addAtHead(val) : linked list 의 첫 번째 요소 전에 value가 val인 node를 추가해주세요. val이 추가되면 이 node는 linked list의 첫 번째 노드가 되는 것입니다.
• addAtTail(val) : value가 val인 node를 linked list의 마지막에 추가해주세요.
• addAtIndex(index, val) : value가 val인 node를 linked list의 index node 바로 전에 추가해주세요. 만약 index가 linked list의 길이와 같다면 제일 마지막에 추가하면 됩니다. 만약 index가 길이보다 길다면, node를 추가하지 말아주세요.
• deleteAtIndex(index) : linked list의 index 번째 node를 삭제해주세요.

4. 정답

• 사실 잘 모르겠으나 추후 해설을 위해서 답을 달아놓는다. 이런거구나~ 정도만 알아두자.

class Node:
    def __init__(self, value):
        self.val = value
        self.next = self.pre = None
  

class MyLinkedList(object):
  
    def __init__(self):
      self.head = None
      self.size = 0
        
    def get(self, index):
      if index < 0 or index >= self.size:
          return -1
      
      current = self.head
      
      for i in range(0, index):            
          current = current.next

      return current.val

    def addAtHead(self, val):
        self.addAtIndex(0, val)

  
    def addAtTail(self, val):
        self.addAtIndex(self.size, val)
      
  
    def addAtIndex(self, index, val):
      if index > self.size:
          return
      
      current = self.head
      newNode = Node(val)
              
      if index <= 0:
          newNode.next = current
          self.head = newNode
      else:                        
          for i in range(index - 1):
              current = current.next
          newNode.next = current.next
          current.next = newNode    
          
      self.size += 1
  
    def deleteAtIndex(self, index):
      if index < 0 or index >= self.size:
          return
      
      current = self.head
      
      if index == 0:
          self.head = self.head.next
      else:
          for i in range(0, index - 1):
              current = current.next
          current.next = current.next.next              

      self.size -= 1