이중 연결 리스트 (Double Linked List) 이중 연결 리스트는 한 노드에 link 멤버가 두 개 있는 연결 리스트를 말합니다. 이전에 설명한 단순 연결 리스트와 원형 연결 리스트는 노드 탐색을 하든, 출력을 하든 항상 다음 노드를 찾아가는 방식이었습니다. 그러나 이 둘은 이전 노드를 탐색하려면 번거로운 과정을 거쳐야 합니다. 실생활에 예를 들자면 일방통행 도로를 생각해볼 수 있겠네요. 가고싶은 장소가 있는데 모르고 지나쳤을 때 다시 돌아가려면 어떻게 해야하나요? 후진해서 지나친 곳을 갈 수 있겠지만, 도로 상황이 번잡하고 무조건 한 방향으로만 움직여야 한다면 빙 돌아서 그 도로를 다시 진입해야겠죠. 지금까지 구현한 리스트는 그런 방식이었습니다. 이중 연결 리스트는 이러한 번거로움을 방지하고자..

원형 연결 리스트 (Circular Linked List) 원형 연결 리스트는 마지막 노드가 첫 번째 노드를 가리키는 리스트입니다. 단순 연결 리스트는 마지막 노드의 link 필드가 NULL이라고 언급했습니다. 하지만, 원형 연결 리스트는 NULL이 아니라 첫 번째 노드 주소가 됩니다. 마지막 노드를 방문해도 첫 번째 노드로 가게 되고 모든 노드가 link 멤버에 NULL이 되어 있지 않은 상태로 연결되어 있는 상태가 됩니다. 이렇게 된다면 노드를 삽입할 때 상수 시간으로 고정이 된다는 장점이 있습니다. 기존에 단순 연결 리스트에서는 끝에 노드를 삽입하기 위해 리스트의 길이만큼 걸리게 되지만, 원형 연결 리스트에서는 헤드 포인터 자체를 옮겨버리면 되기 때문에 훨씬 적은 시간 안에 연산이 이루어지게 됩니다..

리스트란? List가 무엇일까요? 사전을 찾아보지 말고 이번에는 일상적으로 사용하는 것들을 살펴보겠습니다. To-do List 코딩, 독서, 밥 먹기, 친구들과 게임, ... 버킷 리스트 해커톤 우승, 게이밍 컴퓨터 조립, 해외여행, ... 오늘 저녁에 장 볼 목록 토마토, 배추, 김치, 양파, ... 이런 식으로 리스트를 만들어 그 안에 있는 항목들을 정리할 수 있습니다. 데이터도 마찬가지로 이런 식으로 정리할 수 있습니다. 지금까지 스택과 큐를 살펴봤었는데, 큰 범주로 보자면 이것들도 모두 리스트에 속합니다. 배열 배열은 리스트를 구현하는 가장 기본적인 방법입니다. 하지만 배열 특성상 한 번 크기를 지정하면 바꿀 수 없습니다. 따라서 데이터를 추가하고 싶어도 크기가 크지 않다면 문제가 발생할 수 있습..