시냅스

단일 연결 리스트 (Singly Linked List) 단일 연결 리스트는 각 노드들이 한 줄로 연결되어 있는 자료구조이다. 이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다. 연결 리스트는 늘어선 노드의 중간지점에서도 자료의 추가와 삭제가 O(1)의 시간에 가능하다는 장점을 갖는다. (다만, 오늘 구현할 것은 tail을 갖지 않는 linked list로 1번의 반복문을 거치게 된다.) 다만, 기존 링크를 해제하거나 삽입할 때에는 기존 링크의 전이나 다음 노드 관리에 대해 유의해야 한다. 또한 배열이나 트리 구조와는 달리 특정 위치의 데이터를 검색해 내는데에는 O(n)의 시간이 걸리는 단점도 갖고 있다. 특히 단일 연결 리스트는..