자료구조 with 자바

준비중..

자료구조 with 자바

데이터를 효율적으로!

04 연결 리스트(linked-list)

# 연결 리스트(linked-list) ## 목차 1. 연결 리스트란? 2. 장점 3. 단점 4. 종류 5. 구현 ## 1. 연결 리스트란? 연결 리스트란 노드(`node`)의 연결로 이루어진 리스트이다. (리스트: 공백없는 데이터의 나열) ![Imgur](https://i.imgur.com/SoqvrjB.png) ## 2. 장점 1. 데이터의 삽입 삭제 연산이 빠름. `O(1)` <---> 배열: O(n) 2. 리스트 내, 데이터 이동 없음. 3. 큰 메모리공간 필요하지 않음. ## 3. 단점 1. n번째 노드 접근시 `O(n)` 지연 발생. <---> 배열: O(1) 2. 포인터로 인한 메모리 낭비. ## 4. 종류 1. singly linked-list ![Imgur](https://i.imgur.com/SoqvrjB.png) 2. doubly linked-list ![Imgur](https://i.imgur.com/ElsBdWD.png) 3. circularly linked-list ![Imgur](https://i.imgur.com/D5UZnnv.png) ## 5. 구현 아래 명세서를 만족하는 단일 연결 리스트(`Singly Linked List`)를 구현해보자. ### 5.1 명세 단일 연결 리스트는 아래의 명세를 만족한다. + 데이터를 순서 기준(0부터 시작)으로 다룬다. + 데이터의 시작점을 `head`로 가리킨다. + 데이터는 노드(`node`)에 담아 보관한다. + i번째 위치에 데이터를 추가 및 삭제 할 수 있다. + 모든 노드를 차례대로 출력한다. ### 5.2 설계 ![Imgur](https://i.imgur.com/RsHYtUq.png) ### 5.3 코드 코드는 아래의 실습문제를 통해 연습해보자.

Challenge

개념 실습! 학습 내용을 진짜 내 것으로 만들기!