Linked list

기존의 배열을 통한 데이터 정렬을 하게 되면

중간에 입력되는 데이터가 있을 시 그 뒤에 존재하는 모든 데이터의 위치를 옮겨주어야 해서 비효율적이다.

Linked List (연결 리스트)는 그러한 불편함을 해소하고자 도입되었고 어느 위치에있던 상관없이

데이터의 주소값을 통해 데이터의 순서를 확인한다.

보통 Node형태로 구성되어있고

데이터의 맨 앞을 표시하는 head

그리고 next에 그다음 주소값을 입력 시켜준다.

따라서 중간중간에 데이터를 입력시킬때 next의 주소값만 바뀌게 해주면 된다.

ex) {1 3 4 5 6} 에서 "1 3"사이에 "2"를 넣으려면 "1"의 next를 "2"로 바꾸고 "2"의 next를 "3"으로 입력 시켜주면 다른걸 건들지 않고 쉽게 순서를 바꿀수 있다.

tail이라는 데이터 맨 끝을 head에 연결 시켜주어서 돌아가게 할 수 있다.

이중연결 리스트, 양방향 연결 리스트 라고 불린다.

기존의 next 주소뿐만아니라, 추가적으로 previous 주소를 추가해서 양방향으로 왔다갔다 할 수 있다.

동적배열이 훨씬 많이 쓰인다. 그 이유는 연결리스트에는 치명적인 단점이있다.

연결리스트를 쓸때 좋은점