언어 자료구조 알고리즘/디딤돌 Java 언어 Part2 활용

[Java 언어 활용] 3.7 LinkedList 클래스

언제나휴일 2016. 12. 10. 11:37
반응형

[Java 언어 활용] 3.7 LinkedList 클래스


 

 Java 언어에서 LinkedList는 연결리스트를 구현한 클래스입니다. VectorArrayList 클래스처럼 List 클래스를 기반으로 파생한 클래스입니다. 그리고 연결리스트도 배열처럼 선형 자료구조입니다. 하지만 배열은 저장소가 연속적인 메모리에 하나의 덩어리로 할당받지만 연결리스트는 노드 하나에 하나의 데이터를 보관하고 노드 내의 링크에 의해 순서 정보(다음 노드의 위치 정보, 이전 노드의 위치 정보)를 기억하는 자료구조입니다.

[그림 3.3] 배열과 연결리스트

[그림 3.3] 배열과 연결리스트

 

 LinkedList 클래스도 VectorArrayList처럼 List 클래스를 기반으로 파생한 클래스이므로 당연힌 Collection 인터페이스에 약속한 기능을 구현하고 있습니다. 이는 사용방법이 흡사하다는 의미입니다. 하지만 내부적으로 살펴보면 VectorArrayList는 내부 저장소가 배열 형태여서 인덱스 연산에 들어가는 비용이 적습니다. 대신 특정 위치에 추가하거나 삭제하는데 비용이 많습니다. LinkedList는 연결리스트를 구현한 것이어서 인덱스 연산의 속도가 매우 좋지 않습니다. 대신 특정 위치에 추가, 삭제하는데 비용이 O(1)입니다. 그리고 서로 다른 컬렉션을 하나로 병합하거나 분리하는 비용이 적습니다. 이와 같은 주요 특징은 자료구조에 관한 레퍼런스를 참고하시기 바랍니다.

 

 다음은 3.4에서 다루었던 소스 3.4에서 Vector 개체를 생성하는 부분만 LinkedList로 변경한 코드입니다. 다른 부분에 코드를 변경하지 않아도 잘 동작하는 것을 알 수 있습니다.

import java.util.Scanner;

//import java.util.Vector;

//import java.util.ArrayList;

import java.util.LinkedList;

 

public class MemberManager {

        Scanner scan = new Scanner(System.in);

        //Vector<Member> members = new Vector<Member>();

        //ArrayList<Member> members = new ArrayList<Member>();

        LinkedList<Member> members = new LinkedList<Member>();

        ...이후 내용은 차이없음...

 

▷ 소스 3.9 LinkedList를 이용한 회원 관리 프로그램

//Member.java

//회원 클래스

public class Member {

        final int num;

        String name;

        public Member(int num, String name){

               this.num = num;

               this.name = name;

        }

        public int getNum(){

               return num;

        }

        public String toString(){

               return String.format("번호:%d 이름:%s", num,name);             

        }

}

//MemberManager.java

//회원 관리자 클래스

 

import java.util.Scanner;

//import java.util.Vector;

//import java.util.ArrayList;

import java.util.LinkedList;

 

public class MemberManager {

        Scanner scan = new Scanner(System.in);

        //Vector<Member> members = new Vector<Member>();

        //ArrayList<Member> members = new ArrayList<Member>();

        LinkedList<Member> members = new LinkedList<Member>();

        public void Run(){

               int key = 0;

               while((key = selectMenu())!=0){

                       switch(key){

                       case 1: addMember(); break;

                       case 2: removeMember(); break;

                       case 3: searchMember(); break;

                       case 4: listMember(); break;

                       default: System.out.println("잘못 선택하였습니다."); break;

                       }

               }

               System.out.println("종료합니다...");

        }

        int selectMenu(){

               System.out.println("1:추가 2:삭제 3:검색 4:목록 0:종료");

               int key = scan.nextInt();

               scan.nextLine();

               return key;

        }

        void addMember(){

               int num = 0;

               String name="";

               System.out.print("추가할 회원 번호:");

               num = scan.nextInt();

               scan.nextLine();

               System.out.print("회원 이름:");

               name = scan.nextLine();

               Member member =new Member(num,name);

               members.add(member);

               System.out.println(member.toString()+" 생성하였습니다.");

              

        }

        void removeMember(){

               int num = 0;           

               System.out.print("삭제할 회원 번호:");

               num = scan.nextInt();

               scan.nextLine();

               Member member = Find(num);

               if(member == null){

                       System.out.println("존재하지 않습니다.");

                       return;

               }

               members.remove(member);

               System.out.println(member.toString()+" 삭제하였습니다.");

        }

        void searchMember(){

               int num = 0;           

               System.out.print("검색할 회원 번호:");

               num = scan.nextInt();

               scan.nextLine();

               Member member = Find(num);

               if(member == null){

                       System.out.println("존재하지 않습니다.");

                       return;

               }

               System.out.println("검색 결과>>"+member.toString());

              

        }

        void listMember(){

               System.out.println("전체 목록");

               int cnt = members.size();

               System.out.println("회원 :"+cnt);

               for(Member member : members){

                       System.out.println(member.toString());

               }

        }

        Member Find(int num){

               int cnt = members.size();             

               for(Member member : members){

                       if(member.getNum() == num){

                              return member;

                       }

               }

               return null;

        }      

}

//Program.java

//LinkedList 이용한 회원 관리 프로그램

public class Program {

        public static void main(String[] args){

               MemberManager mm = new MemberManager();

               mm.Run();

        }

}

 

▷ 소스 3.9 실행 결과

1:추가 2:삭제 3:검색 4:목록 0:종료

1

추가할 회원 번호:3

회원 이름:홍길동

번호:3 이름:홍길동 생성하였습니다.

1:추가 2:삭제 3:검색 4:목록 0:종료

1

추가할 회원 번호:2

회원 이름:강감찬

번호:2 이름:강감찬 생성하였습니다.

1:추가 2:삭제 3:검색 4:목록 0:종료

4

전체 목록

회원 :2

번호:3 이름:홍길동

번호:2 이름:강감찬

1:추가 2:삭제 3:검색 4:목록 0:종료

3

검색할 회원 번호:2

검색 결과>>번호:2 이름:강감찬

1:추가 2:삭제 3:검색 4:목록 0:종료

2

삭제할 회원 번호:2

번호:2 이름:강감찬 삭제하였습니다.

1:추가 2:삭제 3:검색 4:목록 0:종료

4

전체 목록

회원 :1

번호:3 이름:홍길동

1:추가 2:삭제 3:검색 4:목록 0:종료

0

종료합니다...

 

 이 책에서 Vector, ArrayList, LinkedList 클래스를 사용하는 프로그램을 같은 형태로 작성한 이유는 인터페이스 기반으로 프로그래밍할 때의 장점을 명확히 보여주기 위한 것이 첫 번째 이유입니다. 그리고 두 번째 이유는 비슷한 역할을 하는 클래스들이 있을 때 가급적 공통적인 기능을 이용해서 작성하며 변경 비용을 줄일 수 있다는 것을 얘기하기 위해서입니다. 특정 컬렉션으로 구현해야 할 당위성이 없다면 미래의 유지 보수를 줄일 수 있게 공통적인 기능을 사용하는 습관을 갖기 바랍니다. 물론 성능이나 다른 특정 목적이 있다면 다른 선택을 해야 할 수도 있겠죠.

반응형