자바로 구현한 이중 연결 리스트의 삽입 ◦ 삭제

소개글

절때 중복되지 않은 오리지날 소스입니다.

자바로 구현한 이중연결리스트를 구현한 프로그램으로써

삽입 삭제 디스플레이 종료 검색 기능이 있습니다.
/*
* DoubleEndedLinkedListApp.java
* 클래스 이름 : DoublekedListApp.class
* 소스 코드 : DoubleLinkedListApp.java
* 이중 말단 연결 리스트(Double Linked-List)를 구현한 자바 프로그램이다.
* 이 프로그램은 이중 연결 리스트를 이용하여 다음과 같은 네 가지 동작을
* 수행할 수 있다.
* 1. 삽입 2. 삭제 3. 탐색 4. 출력
* Created on 2006년 10월 15일 (일), 오후 3:51
*/

스크린샷 및 연결리스트의 개념 설명까지 포함되어 있는 완벽 버젼입니다.

소스파일, 설명 파일 스크린샷이 함께 있으며 분량은

20쪽입니다. 후회안하실껍니다.

컴파일 실행환경

자바 가상머신, ms office word

본문내용

리스트는 고정된 길이의 자료(혹은 원소)들을 순차적으로 나열해 놓은 집합을 가리키는 자료구조의 추상적인 개념을 말한다. 리스트는 크게 두 가지의 방법으로 구현할 수 있다. 가장 단순한 방법은 배열을 이용하는 방법이고, 가장 많이 사용되는 방법은 연결 리스트(linked-list)를 이용한 방법이다. 두 방법의 차이점은 단지 구조에서 야기되는 차이점만 존재할 뿐, 리스트의 구현이라는 동일한 목적을 가지고 있다. 즉, 리스트는 하나의 추상 자료형이며 이를 구현하는 방법에는 배열을 이용한 방법과 연결 리스트를 이용한 방법이 있다.
배열을 이용하여 리스트를 구현하는 방법의 최대 장점은 굉장히 간단하게 구현할 수 있다는 점이다. 자료의 최대 개수를 미리 알고 있다면 정적으로 배열의 크기를 생성하여 배열 안에 자료들만 삽입하면 된다. 또한 리스트의 자료들을 출력하거나 특정 자료를 탐색하는 연산은 선형시간(O(n):linear time)안에 수행되며, 배열에서 i번째에 위치한 자료를 탐색하는 연산은 상수 시간(O(1):constant time)안에 수행된다 하지만, 배열을 이용하여 리스트를 구현하는 방법은 여러 가지 단점을 가지고 있다. 임의의 자료를 리스트 중간에 삽입하는 과정과 중간에 존재하는 특정 자료를 삭제하는 과정에서 많은 양의 자료들을 이동시켜야 하는 문제점을 가지고 있다. 또한 초기에 생성된 배열의 크기는 필요에 의해 다시 바꿀 수가 없다. 배열의 크기가 고정되기 때문에 그 일부분만 사용할 때는 메모리가 낭비되고, 배열의 크기보다 더 많은 양의 자료들을 저장하려 할 때는 오버플로우(overflow)가 발생하게 된다. 설령 배열의 크기를 동적으로 할당한다고 해도, 리스트의 최대 크기를 사전에 예측할 수 있어야 한다. 삽입과 삭제에 걸리는 연산속도와 리스트의 크기를 사전에 알아야 하는 제한점 때문에 일반적으로 배열을 이용하여 리스트를 구현하지는 않는다. 배열보다는 연결리스트를 주로 많이 사용한다.

압축파일 내 파일목록

R1_2002174264_이중연결리스트.doc
이중연결리스트/DoublyLinkedList.class
이중연결리스트/DoublyLinkedListApp.class
이중연결리스트/DoublyLinkedListApp.java
이중연결리스트/LinkNode.class
이중연결리스트/LinkSentinelNode.class

참고 자료

없음