![]()
1. 이중 연결 리스트란? 이중 연결 리스트란 단일 연결리스트와 다르게 양방향으로 노드가 이어진 리스트이다. 이중 연결 리스트는 이전 노드와 이후 노드가 이어져 있기 때문에 삽입 삭제 연산 시 이전, 이후 노드를 저장하지 않아도 되기 때문에 훨씬 유연하게 사용할 수 있다. 2. 이중 연결 리스트 구현 이번 이중 연결 리스트 구현은 Head와 Tail에 data가 들어있지 않은 더미(dummy)노드를 사용해서 구현했다. 2-1. 구조체 및 클래스 선언부 이중 연결 리스트는 노드 두개가 서로 연결 되어있기 때문에 이전 노드와 다음 노드를 포인팅하는 prev, next 구조체 포인터를 선언해줬다. struct Node { Node* prev; Node* next; int data; }; class Doubly..
![]()
1. 단일 연결 리스트란? 각 요소들이 데이터부분과 다음 값 주소를 포인팅하는 노드라는 형태로 이루어져 있으며 체인 형태로 선형으로 이루어진 자료구조이다. 값을 추가할 때 배열은 정해진 사이즈를 넘으면 Overflow가 발생하지만 Linked List는 동적으로 할당해서 노드들을 이어주면 되기 때문에 메모리 사이즈 문제에서 벗어날 수 있다. 하지만 노드들이 서로 체인형태로 이어져 있어 배열처럼 인덱스 개념으로 접근이 불가하기 때문에 순회하여 값을 찾아야 하으로 탐색에 있어서는 배열보다 느리다. 하지만 값을 중간에 넣는 경우 배열은 중간에 값을 삽입하고 한칸씩 뒤로 미뤄줘야 하기 때문에 원소의 갯수에 따라 시간이 차이가 나는 방면, 연결 리스트의 경우 단지 노드의 포인팅만 바꿔주면 되기 때문에 최악의 경우..
