연결 리스트

Linked List

단방향 연결 리스트

Node를 단방향으로 연결

head는 첫번째 Node를 가르키고 Node의 멤버변수로 다음 노드를 가르키는 Node next 변수가 존재함

장점 : 데이터를 추가 삭제가 배열보다 용의하다. 메모리를 효율적으로 관리 할 수 있다 (배열을 크기가 정해져 있으나, 리스트는 존재하는 노드수 만큼만 메모리를 차지하기에)

단점 : next변수에 대한 추가 메모리가 필요함.

Doubly Linked List

양방향 연결 리스트

리스트의 head 와 tail을 가르키는 변수가 있고 각 Node의 멤버변수로 이전과 다음 노드를 가르키는 변수가 존재함

장점 : 양방향 검색이 가능. 단방향 리스트보다 노드 삭제할 때 효율적임. (해당 노드의 prev 와 next의 노드를 연결하면 됨)

단점 : 메모리가 필요함.

Circular Linked List

환상 연결 리스트

단방향 연결 리스트의 마지막 노드의 다음을 NULL 넣지 않고 첫번째 노드를 가르켜 리스트가 원형 연결이 되도록 함.

링크드 리스트 비교 분석

http://imtaeheewon.tistory.com/14