1. Linked List
- 주 사용 : 일렬로 연결된 데이터를 저장할 때 사용된다.
- Linked List는 다음 데이터의 주소를 가지고 있다.
2. Linked List와 배열의 차이
- 배열의 경우
- 배열은 크기를 정하면 다시 변경할 수 없다.
- Linked List의 경우
- 1. 중간 데이터 삽입 가능하다. (데이터 A 대신 데이터 D로 교체 가능하다.)
- 2. 링크를 뺄 수도 있다.(데이터 D를 뺄 수도 있다.)
<LinkedList와 배열의 차이점 -정리>
- LinkedList에서 노드 D는 Linked List에서 삭제되었지만 메모리를 차지하고 있다.
- 자바에서는 이렇게 안 쓰이는 변수를 처리해준다. ( 알아서 처리해줌)
- c/c++ 경우에는 안 쓰겠다고 명시해야 한다.
- LinkedList는 주소를 일일이 찾아다녀야 해서 배열보다 속도가 느릴 수 있다.
- 하지만, LinkedList를 배열로 구현해야 한다면 처음부터 다시 배열을 새로 만들어야 하는 번거로움이 크다.
3. LinkedList -단방향/양방향
- 단방향
- 한 쪽 방향으로 이동한다.
- 오직 다음 데이터의 주소를 알고 있게 된다.
- 양방향
- (추가적으로) 앞의 데이터의 주소를 알고 있다.
- 중간에 데이터 삽입/삭제가 가능하다.
<LinkedList의 단방향/양방향 -정리>
- 단방향
- 한 쪽 방향이라, 헤더 주소 하나만 저장한다.
- 양방향
- 양쪽으로 포인터를 저장하고 있어서 맨 끝의 노드를 삽입할 때 일부러 끝노드까지 안 찾아도 된다.
- (단방향의 경우, 맨 끝의 노드를 삽입하기 위해 일부러 끝노드까지 찾아가야 한다.)
- 공간의 효율성을 따지자면, 굳이 양방향이 필요없는 경우에 사용하면 낭비된다.
댓글