연결 리스트

지침

이중 연결 리스트를 구현해요.

연결 리스트는 배열과 마찬가지로 단순한 선형 자료 구조예요. 큐, 스택, 연관 배열처럼 흔히 쓰이는 여러 자료 구조를 연결 리스트로 구현할 수 있어요.

연결 리스트는 노드라고 부르는 데이터 원소들의 모음이에요. 단일 연결 리스트에서는 각 노드가 값과 다음 노드로의 링크를 가지고 있어요. 이중 연결 리스트에서는 각 노드가 이전 노드로의 링크도 가지고 있어요.

이제 이중 연결 리스트를 직접 구현해 볼 거예요. 값과 다음 및 이전 노드에 대한 포인터를 담는 Node를 구현해요. 그다음 첫 번째와 마지막 노드에 대한 참조를 담고, 항목을 추가하고 제거할 수 있는 배열과 비슷한 인터페이스를 제공하는 List를 구현해요.

• push (뒤에 값을 삽입해요);
• pop (뒤에서 값을 제거해요);
• shift (앞에서 값을 제거해요).
• unshift (앞에 값을 삽입해요);

구현을 단순하게 유지하기 위해, 테스트에서는 오류 상황을 다루지 않아요. 구체적으로, 빈 리스트에 대해 pop이나 shift를 호출하는 일은 없어요.

위키백과의 연결 리스트 문서에서 더 자세히 읽어볼 수 있어요.