자료구조 연결리스트

해당 자료는 유튜브 신찬수 한국외대 교수님 강의를 시청하고 정리했으며
코딩테스트 합격자되기 자바스크립트편 도서를 읽고 추가적으로 정리되어 있습니다. 🙏🏻

배열 vs 연결리스트

• 배열은 메모리 공간에 순차적으로 배치되므로 인덱스로 접근이 가능하지만,
• 연결리스트는 연속된 메모리 공간에 들어있는 것이 아닌 메모리상에서 흩어져 있어서 상수시간 접근이 불가능

연결리스트 (Linked List)

• 노드란 data 값(key)과 주소의 값(link)로 구성된 한쌍을 말하며,
  노드와 링크로 연결된 자료구조를 말한다.
• 가장 앞의 노드를 헤드 노드(head node)로 칭한다.
• 마지막 노드에는 None/null이 있다

장점

• 배열은 중간에 데이터를 삽입하게 되면 뒤에 있는 데이터들이 n번씩 밀려나면서 이동해야하지만, 연결리스트는 중간에 새로운 노드 삽입 후 다시 연결만 하면 된다. 즉, 두 개의 링크 주소만 바꾸면 된다.
• 따라서 insert 작업에는 O(1)(상수시간)이 걸린다

연결리스트의 종류

• 한 방향, 양 방향 연결리스트 2종류가 있음

한 방향 리스트

• 링크가 한쪽 방향으로만 연결되어 있는 것으로, 한 방향으로만 갈 수 있고 반대 방향으로는 갈 수 없다.

양 방향 리스트

• 양쪽 방향으로 링크가 있어서 노드의 양쪽 방향으로 모두 이동할 수 있다.

구현하기

유튜브 강의는 파이썬으로 작성되어 있습니다.

class Node:
  def __init__(self, key = None):
    self.key = key
    self.next = None
  def __str__(self):
    return str(self.key) //print(v.key) 대신 print(v)로 쓸 수 있다.

사용 예시

a = Node(3)
b = Node(9)
c = Node(-1)

a.next = b
b.next = c

• c 노드를 테일 노드(tail node)라고 부른다.