독학사2단계_자료구조_4장 연결리스트

4장. 연결리스트(Linked List)

가) 연결 리스트 필요성

·순서 리스트를 배열을 이용해서 구현하게되면 메모리 사용 측면에서의 비효율적인 문제점이 나타난다.

삽입과 삭제 연산 후에 연속적인 물리 주소를 유지하기 위해 원소들을 이동시키는 작업이 소요된다는 점이 부담

이러한 점을 개선한 자료 표현방법이 연결 리스트이다.

나) 단순 연결 리스트

·각 리스트에 포인터를 포함시킨 표현 방법이다.

·각 항목을 노드라고한다. 노드의 구성은 다음과 같다.

Info

Next

Info에는 데이터가 들어있고 Next는 다음 항목의 노드를 가르키는 포인터가 들어있다.

·노드의 추가/삭제 시에 새로운 노드를 생성해서 삽입하고자하는 원소의 앞/뒤 노드와 연결만 하기에

 순서 리스트에서 발생하는 원소들의 이동이 일어나지 않게 된다.

다) 동적 연결된 스택과 큐

[http://lsh1894.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-8%EA%B0%95-%EB%8F%99%EC%A0%81-%EC%97%B0%EA%B2%B0%EB%90%9C-%EC%8A%A4%ED%83%9D%EA%B3%BC-%ED%81%90-%EC%97%B0%EA%B2%B0%EB%A6%AC%EC%8A%A4%ED%8A%B8]

라) 비사용 기억 공간

마) 연결 리스트의 응용

바) 연결 리스트의 기타 연산

사) 이중 연결 리스트

아) 일반 리스트

1. NULL

·NULL