[Datastructure]Linked List

링크드 리스트는 자료를 표현함에 있어서 노드와 노드사이의 연결을 이용하여 표현한다.

노드는 실제 표현할 data와 다음 노드를 가리킬 변수로 구성되어 있다.

next라는 변수로 다음 노드를 가리키면 된다.

head 변수는 리스트의 시작점을 가리키는 변수이고

리스트의 끝 부분(tail)을 표현하는것은 해당 노드의 next변수에 null을 할당하면 된다.

 

Linked list의 property와 method는 

property : head, tail, current 

method : insert, delete

등이 있다.

insert

1. 새로운 노드와 그 노드를 삽입할 인덱스를 정한다.
2. data를 넣어준다.
3. head부터 순회하면서 삽입합 인덱스를 찾는다.
4. 삽입할 인덱스가 가리키는 노드의 참조값을 변수로 가지고 있는다.
5. 삽입합 인덱스에 해당하는 노드 바로 전 노드의 next값을 새로운 노드의 참조값으로 준다.
6. 새로운 노드의 next값을 4.에서가지고 있는 참조값에 할당한다.

delete

1. 삭제할 노드의 인덱스를 정한다.
2. head부터 순회하면서 삭제하기 전의 노드와 삭제할 노드를 찾는다.
3. 삭제전의 노드의 next가 삭제 다음 노드의 참조값을 가리키게 한다.
4. 삭제할 노드를 지운다.(혹은 삭제할 노드의 next를 null로 해준다.)