자료구조 한방향 연결리스트

해당 자료는 유튜브 신찬수 한국외대 교수님 강의를 시청하고 정리되어 있습니다. 🙏🏻

한방향 연결리스트

삽입 연산 With Python(강의)

pushFront, pushBack

class SinglyLinkedList:
  def __init__(self):
    self.head = None
    self.size = 0
    
  def __len__(self):
    return self.size
    
  def pushFront(self, key):
    new_node = Node(key)
    new_node.next = self.head;
    self.head = new_node
    self.size += 1
    
  def pushBack(self, key):
    v = Node(key)
    if len(self) == 0:
      self.head = v
    else:
      tail = self.head
      while tail.next != None:
        tail = tail.next
      tail.next = v
    self.size += 1

삭제 연산 With Python(강의)

popFornt

def popFront(self):
  if len(self) == 0:
    return None
  else:
    x = self.head
    key = x.key
    self.head = x.next
  self.size -= 1
  del x
  return key

popBack

def popBack(self):
  if len(self) == 0: return None
  else: # running techinque
    prev, tail = None, self.head
    while tail.next != None:
      prev = tail
      tail = tail.next
    if len(self) == 1:
      self.head = None
    else
      prev.next = tail.next # None
      key = tail.key
      del tail
      self.size -= 1
      return key

탐색 연산 With Python(강의)

def search(self, key):
  # key 값의 노드를 리턴, 없으면 None 리턴
  v = self.head
  while v.next != None:
    if v.key == key:
      return v
    v = v.next
  return None # or return v (== None)

한 방향 연결 리스트를 for...of 루프로 순회하는 법, 즉 제너레이터와 이터러블 구현을 설명해줄게.

제너레이터

• 한 방향 연결리스트를 for ..of 루프로 순회하려면 이터러블(iterable) 이어야 한다. (pytho,js 모두 동일)
• 따라서 yield가 포함된 제너레이터 함수를 사용하여 간단하게 이터러블을 만든 후 사용해야한다.

With JS 코드

class MyList
...

// 해당 코드 !!
*[Symbol.iterator]() {
    let current = this.head;
    while (current !== null) {
      yield current.value;
      current = current.next;
    }
  }

탐색 사용법

const list = new MyList();
for (let value of list) {
  console.log(value);
}

• 클래스에 위와 같은 이터러블이 생성되어있다면 그 클래스로 만든 객체 즉 한 방향 연결리스트가 for문으로 순회가 가능하게 된다!!!

한방향 연결리스트의 수행 시간

• pushFront: O(1)
• popFront: O(1)
• pushBack: O(n)
• popBack: O(n)

pushBack과 popBack은 tail을 쫓아가야하기 때문에 n번 필요