기본 콘텐츠로 건너뛰기

개발 공부 - 연결 리스트의 구조와 사용

* 공부용의 자유로운 글씨😀
『가장 쉬운 독학 알고리즘 첫걸음 - C&자바편』 공부용이다.

5장부터는 구조체 개념이 나온다.
구조체는 여러 데이터를 하나로 묶은 것인데, 구조체 기반의 배열도 만들 수 있다.
구조체를 활용해서 연결 리스트를 구현 할 수 있는데 (= 리스트)
배열의 한 요소가 어디에 연결되어있는지에 관한 정보를 가지고 있다.
자바에서는 레퍼런스 개념임!

연결 리스트를 사용하면 요소의 물리적 순서와 관계없이 연결 정보로 요소의 논리적 순서를 결정한다.
연결 리스트는 그냥 배열과 달리 요소의 삽입 / 제거가 효율적이다.

만약에 
서울 - 천안아산 - 대전 - 동대구 - 부산 이라는 연결 리스트가 있을 때 ,
서울 뒤에 광명을 끼우려면 원래 배열은 한칸씩 다 >> 를 해줘야 함.

근데 연결 리스트는 그냥 연결 정보값만 수정하면 됨.
서울 - 천안아산 - 대전 - 동대구 - 부산 - 광명 
순서로 삽입했었어도, 
head(실제 논리적 순서의 시작점) 가 서울일 때, head가 가리키는 것을 광명으로 하면 됨.

삭제 시에도 하나 지우고 배열은 한 칸씩 다 << 를 해줘야 하는데,
연결 리스트는 그냥 연결 정보를 가리키던 값들을 수정해 주면 끝임.

이게 배열보다 좋은 것 같지만, 사실 요소 가져올 때 처리가 생각보다 많이 필요해서
단점도 있음.

연결 리스트에서는 만약에 세번째 위치한 값을 가져오려면 이렇게 해야 함.
1) head를 참조해서 첫 번째 요소가 a[2] 임을 확인함
2) a[2] 를 참조하여 논리적 순서의 두 번쨰 요소가 a[4] 임을 확인함
3) a[4] 를 참조하여 세 번째 요소가 a[1]이고, 요소값이 대전임을 확인함

이런 식으로 논리적인 순서를 다 타야 하기 떄문에 요소 검색 시에는 시간이 많이 걸린다.

사실 자바는 그냥 연결 리스트를 LinkedList list = new LinkedList(); 로 선언하면 만들 수 있긴 한데, 공부를 위해서 직접 만든다고 한다.

(주의) 공부용이라 C 비슷하게 예제가 나왔다고 한다.
생성자도 안 쓰고, 접근 제어도 public으로 해버림! 
* 찐으로 구현할 때는 이렇게 하지 말 것.

list랑 head는 함수 외부에서 선언해서 사용한다고 한다.

이걸 의사 코드로 만들어 보면 아래와 같다.


이걸 코드로 짜면 아래와 같다.

class StationList{
    public String name; //역이름
    public int next; //연결 정보
}

public class 연결리스트 {
    public static StationList [] list = new StationList[10];
    public static int head;

    public static void main(String[] args) {


        initStationList();
        printStationList();
    }

    public static void initStationList(){
        for(int i = 0; i< list.length; i++){
            list[i] = new StationList();
        }

        list[0].name = "부산";
        list[0].next = -1;
        list[1].name = "대전";
        list[1].next = 3;
        list[2].name = "서울";
        list[2].next = 4;
        list[3].name = "동대구";
        list[3].next = 0;
        list[4].name = "천안아산";
        list[4].next = 1;

        head = 2; //서울을 head로 설정함
    }  

    public static void printStationList(){
        int idx = head;
        while (idx != -1){
            //-1인 부산을 맨 마지막으로
            System.out.println(idx + " 는 " + list[idx].name);
            idx = list[idx].next;
        }
    }


}


insertStationList 를 의사코드로 작성하면 아래와 같다.



자바로 구현하면 아래와 같다.

class StationList{
    public String name; //역이름
    public int next; //연결 정보
}

public class 연결리스트_추가 {
    public static StationList [] list = new StationList[10];
    public static int head;

    public static void main(String[] args) {

        initStationList_();
        printStationList();
        System.out.println("---------------------------");
        initStationList(5, "광명", 2);
        printStationList();
    }

    public static void initStationList_(){
        for(int i = 0; i< list.length; i++){
            list[i] = new StationList();
        }

        list[0].name = "부산";
        list[0].next = -1;
        list[1].name = "대전";
        list[1].next = 3;
        list[2].name = "서울";
        list[2].next = 4;
        list[3].name = "동대구";
        list[3].next = 0;
        list[4].name = "천안아산";
        list[4].next = 1;

        head = 2; //서울을 head로 설정함
    }  

    public static void initStationList(int insIdx, String insName, int prevIdx){
   
        list[insIdx].name = insName;
        list[insIdx].next = list[prevIdx].next; //앞 연결 요소 설정
        list[prevIdx].next = insIdx;
       
    }  

    public static void printStationList(){
        int idx = head;
        while (idx != -1){
            //-1인 부산을 맨 마지막으로
            System.out.println(idx + " 는 " + list[idx].name);
            idx = list[idx].next;
        }
    }


}



이렇게 광명을 껴넣을 수 있다.
위치는 list[5] 인데 2 뒤에 넣어야 하니까 서울 뒤에 들어감

이렇게 만든 상태에서 요소를 삭제도 가능한데, 의사 코드는 아래와 같다.
삭제 시 필요한 것은 삭제할 요소의 인덱스, 삭제할 요소의 하나 앞 요소 인덱스이다.



구현하면 아래와 같다.

class StationList{
    public String name; //역이름
    public int next; //연결 정보
}

public class 연결리스트_추가 {
    public static StationList [] list = new StationList[10];
    public static int head;

    public static void main(String[] args) {

        initStationList_();
        printStationList();
        System.out.println("---------------------------");
        initStationList(5, "광명", 2);
        printStationList();
        System.out.println("---------------------------");
        deleteStationList(5, 2);
        printStationList();
       

    }

    private static void deleteStationList(int delIdx, int prevIdx) {
        list[prevIdx].next = list[delIdx].next;
        //삭제할 요소의 하나 앞 인덱스를 현재 삭제할 요소의 인덱스로 바꿔준다.
        // 그러면 삭제할 요소는 연결 리스트에서 빠짐
    }

    public static void initStationList_(){
        for(int i = 0; i< list.length; i++){
            list[i] = new StationList();
        }

        list[0].name = "부산";
        list[0].next = -1;
        list[1].name = "대전";
        list[1].next = 3;
        list[2].name = "서울";
        list[2].next = 4;
        list[3].name = "동대구";
        list[3].next = 0;
        list[4].name = "천안아산";
        list[4].next = 1;

        head = 2; //서울을 head로 설정함
    }  

    public static void initStationList(int insIdx, String insName, int prevIdx){
   
        list[insIdx].name = insName;
        list[insIdx].next = list[prevIdx].next; //앞 연결 요소 설정
        list[prevIdx].next = insIdx;
       
    }  

    public static void printStationList(){
        int idx = head;
        while (idx != -1){
            //-1인 부산을 맨 마지막으로
            System.out.println(idx + " 는 " + list[idx].name);
            idx = list[idx].next;
        }
    }


}


이러하다!

이건 사실 단방향 연결 리스튼데, 양방향도 있고 뭐 원형도 있고 그러하다...
양방향 : 앞/뒤 정보 가지고 있음
원형 : head가 tail을 가리키는 구조라 한바퀴 돌고 있음


* 사실 개념상 알아두고 자바는 그냥 LinkedList를 쓰자...
(공부용으로는 코딩 테스트 연습용 풀 때 복기 목적으로 가끔 짜 보면 좋음)





댓글

이 블로그의 인기 게시물

Ebook - 전자책 drm 상관 없이 pdf로 만들기

yes24와 교보문고에서 ebook을 구매 해야 했는데 너무 불편하고, 필기가 매우 화날 정도로 안 좋아서 원시적으로 사용하기로 했다. 1. 목적 : ebook에서 필기 및 사용이 불편하여 pdf로 변환  2. 용도 : 개인 사용 목적이며 화질이 다소 저하되어도 필기만 용이하면 상관 없음 3. 방법 1) 휴대폰 및 카메라로 동영상을 촬영했다. DRM 때문에 프로그램으로는 촬영이 안 되는 것을 확인했다. (사실 개인 사용 목적이면 기본 화면 캡쳐를 사용해도 된다...) 2) 마우스 클릭 해주는 매크로를 사용했다. (1) key_macro.exe > https://blog.daum.net/pg365/250 듀얼 모니터에서 위치 이탈 현상이 있긴 해도 괜찮았다. (2) AutoClick.exe > http://bestsoftwarecenter.blogspot.com/2011/02/autoclick-22.html 이 걸로 잘 사용했다. 3초마다 한 번 클릭하도록 사용했다. 3) 동영상을 이미지로 변경해주는 프로그램을 사용했다. Free Video to JPG Converter > https://www.dvdvideosoft.com/products/dvd/Free-Video-to-JPG-Converter.htm (240826: 다운로드 시 정상적으로 되지 않아서 URL 수정) 일 하면서 듀얼 모니터에 켜 놨는데 속도가 괜찮았다. * Every frame 으로 사용해야 한다. 4) 중복 사진 제거해주는 프로그램을 사용했다. VlsiPics  > http://www.visipics.info/index.php?title=Main_Page 생각보다 느리니 퇴근시에 걸어놓고 가면 된다. 한번 play가 끝나면 Auto-select 하고 Delete 하면 된다. 5) 이미지를 일괄 Crop 작업 해주는 프로그램을 사용했다. JPEGCrops > https://jpegcrops.softonic.kr/ * https://joker1209.tistory.co

개발 공부 - json JSONObject 사용 시 백슬래시(\), 원화 표시(\) 제거 및 치환

import org.json.simple.JSONObject; String dataString = new String(authData.toJSONString()); dataString = dataString.replaceAll("\\\\", ""); String 으로 안 바뀌는 가 싶어서 String 으로 변환 해 주고 작업 하였다. 사실 toJSONString 해도 정상 동작 해야 하는데 이유를 잘 모르겠음. 그리고 나서 다시 이클립스 구동 하니 toString 도 먹은 걸로 봐서 이상하다고 생각! String dataString = authData.toString(); dataString = dataString.replaceAll("\\\\", ""); 어쨌든 백 슬래시 제거를 해줘야 하는데 \\ 도 아니고 \\\\를 해야 변환이 가능했다는 결말이었습니다. 참고 : https://stackoverflow.com/questions/15450519/why-does-string-replace-not-work/15450539 test =test.replace("KP", "");  replace 후에 담아 주지 않으면 적용이 안 됩니다!

개발 공부 - OracleXETNSListener 서비스가 로컬 컴퓨터에서 시작했다가 중지되었습니다.

여러 가지 요인이 있지만 PC 이름 변경시 OracleXETNSListener 서비스 시작이 불가능합니다. 고치는 법은 C:\oraclexe\app\oracle\product\11.2.0\server\network\ADMIN 와 같은 설치 경로에서 listener.ora와 tnsnames.ora 의 pc명을 바꾼 PC명으로 바꿔주면 됩니다. 그래도 안 된다면 cmd 창에서 services.msc 를 입력 후 OracleXETNSListener 서비스를 시작 시키면 됩니다. 오류명: OracleXETNSListener 서비스가 로컬 컴퓨터에서 시작했다가 중지되었습니다. 일부 서비스는 다른 서비스 또는 프로그램에서 사용되지 않으면 자동으로 중지됩니다. 참고한 사이트들 1. http://blog.naver.com/visioner7/120165951652 2. http://database.sarang.net/?inc=read&aid=6819&criteria=oracle&subcrit=&id=&limit=20&keyword=ora-12560&page=5 이런 걸 보면 오라클은 앙칼진 시골 아가씨야