연결리스트(Linked List)는 한방향과 양방향이 있다.
연결리스트는 노드(node)끼리 연결된 형태로 되어있는데, 이 노드 안에 key와 link가 있고, key는 데이터값이다.
가장 첫 노드를 head node라고 하고 맨 마지막 노드는 link가 없어 None을 향한다. link는 다른 노드의 주소를 저장하고있다.
배열에 비해 좋은 점은, 배열은 어떤 값을 중간에 삽입할때 그 값 뒤에있는 값들을 전부 다 뒤로 한칸씩 밀어서 O(n)이지만,
연결리스트는 링크 2개만 바꾸면 되서 O(1)이다. 대신 삽입되는 노드의 앞뒤 노드가 뭔지 알고 있어야 한다.
한방향 연결리스트는 말그대로 한방향으로만 link가 있다.
양방향 연결리스트는 노드에 link가 두개있어서 양방향으로 이동이 가능하다.
가장 첫 노드 : head node
가장 마지막 노드 : tail node
공부일기