3. 연결리스트(linked list)

1. 개념

연결리스트(linked list)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조이다. 연결리스트는 단일 연결 리스트, 이중 연결 리스트, 원형 연결 리스트 등이 있다. 예를 들어, 한 반에 있는 학생들의 자료를 저장한다면, 학생 1명당 자료를 노드로 만들고, 1번 학생의 자료에 2번학생의 자료가 어디있는지 표시를 해놓는 방식이다. 

배열에 비해서, 연결리스트는 노드를 뒤에 연결하거나 중간에 껴놓는 것은 쉽고, 데이터를 추가/삽입 및 삭제가 용이하다. 하지만, 배열은 특정한 자료를 불러내기가 편리한 반면, 연결리스트는 자료 번호가 없고, 연결 관계만 있기 때문에 특정한 노드를 불러내기가 어렵다. 또한 연결리스트는 순차적으로 탐색하지 않으면 특정 위치의 요소에 접근할 수 없어 탐색 속도가 떨어진다.

자료의 처음을 head라 하고, 끝을 tail이라 한다.

2. 구현(단일 연결 리스트)

node와 linkedlist class를 따로 만들었다. 

• add - data를 삽입하는 메소드이고, 새로운 node를 만들어서 head가 없다면 head에 맨처음 node를 넣어주고, 아니면 next가 null될때까지 이동해서 node를 추가해주었다. 마지막부분의 next는 null이기 때문이다.
• remove - data를 제거하는 메소드이고, position까지 순차적으로 탐색해서 삭제를 해준다.
• search - position에 있는 노드를 찾는 메소드이다. 순차적으로 탐색해서 찾는다. 

출처 - 나무위키, 유투브, 위키피디아(영어), 위키피디아(한글)