2.연결리스트

연결리스트

데이터를 순서대로 나열한 자료구조
연결리스트에서는 특정 인덱스를 상수 시간에 접근할 수 없다.
연결리스트의 장점은 리스트의 시작 지점에서 아이템을 추가하거나 삭제하는 연산을 상수 시간에 할 수 있다.

연결리스트 만들기

단방향 연결리스트 구현, 연결리스트에 접근할 때 head 노드의 주소를 참조
Node 클래스를 포함하는 LinkedList 클래스를 작성하여 여러 객체가 접근하는 경우,
연결리스트를 참조하는 도중에 head가 바뀌는 경우, 어떤 객체들은 이전 head를 계속 가리키고 있는 문제
head Node 변수를 단 하나만 정의 되어있도록하여 문제점을 해결

단방향 연결리스트에서 노드 삭제

단방향과 양방향 연결리스트의 차이로 인한 유의사항
1. null 포인터 검사
2. 필요하면 head와 tail 포인터도 갱신해야 한다.

재귀 문제

연결 리스트 가운데 상당 수는 재귀 호출에 의존한다.
하지만 재귀 호출 깊이가 n이 되는 경우, 해당 재귀 알고리즘이 적어도 O(n)만큼의 공간을 사용한다.
모든 재귀 알고리즘은 반복적 형태로도 구현될 수도 있지만, 반복적 형태로 구현하면 복잡해질 수 있다.

면접 문제

중복 없애기
- 해시테이블은 생각해 보았는지?
- 연결 리스트를 한 번만 읽어서 해결할 수 있어야 한다.
- 추가 공간 없이 O(N^2) 시간에 할 수 있을 것이다. 포인터 두 개를 사용해 보기, 두 번째 포인터는 첫 번째 포인터 앞에서 검색하는 방식
뒤에서 K번째 원소
- 연결리스트의 크기를 알고 있는 경우? 마지막에 K 번째 원소를 찾는 것과 X번째 원소를 찾는 것의 다른점?
- 연결리스트의 크기를 모르는 경우? 계산해서 알아낼 수 있는가? 이 방법이 수행시간에 어떤 영향을 끼치는가?
- 재귀로 구현하기 마지막에서 K-1 번째 원소를 찾을 수 있다면, K번째 원소도 찾을 수 있지 않는가?
- 값을 여러 개 반환하는 것이 유용할 수도 있다. 어떤 언어에서는 값을 여러 개 반환할 수 없지만, 이를 해결하는 방법은 모든 언어에서 다 제공한다.
  해결 방법에는 무엇이 있을까?
- 순환적 방법으로 할 수 있는가? 두 포인터가 인접한 노드를 가리키고 있고, 같은 속도로 연결 리스트를 순회한다고 가정할 때
  포인터 하나가 연결 리스트의 끝에 도달 했을 때 다른 하나는 어디에 있겠는가?
중간 노드 삭제
- 리스트 1 -> 5 -> 9 -> 12를 그리고 9를 지우면 1 -> 5 -> 12 가 되는데 9 노드에만 접근할 수 있다?
분할
- 원소의 상대적인 순서가 달라져도 되는 경우를 먼저 생각
- 피벗보다 작은 원소는 피벗보다 큰 원소 이전에만 위치하면 된다.
리스트의 합
- 연결리스트를 정수형으로바꾸고, 합을 계산하고, 다시 새로운 연결리스트로 바꿔도 된다.
  그리고나서 정수로 바꾸지 않고 문제를 푸는 방법을 찾을 수 있는지도 확인
- 재귀를 사용해보기, A = 1 -> 5 -> 9 (951), B = 2 -> 3 -> 6 -> 7 (7632)
  두 개의 리스트와 리스트의 나머지 (5 -> 9와 3 -> 6 -> 7)에서 동작하는 함수가 있을 때, sum 메서드를 만들 수 있는지?
  sum(1->5->9, 2->3->6->7)과 sum(5->9, 3->6->7)에는 무슨 관계가 있는지?
- 길이가 같지 않은 연결리스트를 고려하기
- 9 -> 7 -> 8과 6 -> 8 -> 5 같은 연결리스트에서도 잘 작동하는지 확인
- 연관 문제: 두 연결리스트의 길이가 같지 않을 때, 어떤 연결리스트의 헤드는 1000의 자리수를 가리키는 반면에 다른 연결리스트의 헤드는 10의 자리수를 가리키는 문제가 발생할 수 있다.
- 두 연결리스트의 길이를 같게 만들면 어떠한가? 값을 변경하지 않으면서 두 연결리스트의 길이가 같아지도록 수정하는 방법이 있는가?
회문
- 회문(palindrome)은 앞으로 읽으나 뒤로 읽으나 같은 것을 말한다. 연결리스트를 뒤집으면 어떻게 되겠는가?
- 스택을 사용해보기
- 연결리스트의 길이를 알고있다고 가정하라. 재귀적으로 구현할 수 있겠는가?
- 재귀를 사용하면(리스트의 길이를 알고 있다), 가운데 지점이 기본 사례가 된다.
- isPermutation(middle)은 참이 된다. middle의 바로 왼쪽 노드인 x를 살펴보자.
- x -> middle -> y의 형태가 회문인지 확인하려면 무엇을 해야 할까? 이 부분이 회문이라고 하자.
- 그 이전 노드인 a는 어떤가? x -> middle -> y가 회문일 때, aLazyInitialization -> x -> middle -> y -> b가 회문인지는
  어떻게 확인할까?
- 이전 힌트로 돌아가보라. 값 여러 개를 반환하는 방법이 있다는 사실을 기억하라. 새로운 클래스를 만들어서 할 수 있다.
교집합
- O(A+B)시간과 O(1)공간에 풀 수 있다. 즉,해시 테이블이 필요없다.
- 예제를 사용하면 도움이 될 것이다. 연결리스트가 교차하는 그림을 그려 보라. 또한 값이 같은 두 개의 동일한 연결리스트를 교차하지 않게 그려보기.
- 먼저 교차하는 지점이 있는지를 어떻게 확인할 것인지부터 생각해 보자.
- 서로 교차하는 두 개의 연결리스트의 마지막 노드는 항상 같다. 교차하는 노드 이후의 노드는 모두같다.
- 마지막 노드를 비교함으로써 두 연결리스트가 교차하는지 아닌지 판단할 수 있다.
- 이제 어디서 연결리스트가 교차하는지 찾아야 한다. 연결리스트의 길이가 같다고 가정하자. 어떻게 할 수 있겠는가?
- 두 연결리스트의 길이가 같다면, 공통된 원소를 찾을 때까지 같이 하나씩 읽어나가면 된다.
- 리스트의 길이가 다른 경우에는 이를 어떻게 조절할 수 있을까?
- 두 연결리스트 길이의 차이를 사용하기
- 길이가 긴 연결리스트에서 포인터를 두 리스트의 길이의 차이만큼 앞에 놓고, 길이가 짧은 연결리스트에서는 포인터를 맨 앞에 놓는다.
- 그 다음에 마치 두 연결리스트의 길이가 같은 것처럼 알고리즘을 적용할 수 있겠는가?
루프 발견
- 이 문제는 두 부분으로 나뉜다. 첫 번째, 연결리스트에 루프가 있는지 확인 한다. 두 번째, 루프가 어디서 시작하는지 확인하라.
- 사이클이 있는지 확인하려면, "Runner"기법을 사용해 볼 수 있다. 하나의 포인터를 다른 하나보다 빠르게 움직이는 방법
- 포인터 두 개를 사용해서 하나를 다른 하나보다 두 배 빠르게 움직일 수 있다.
- 사이클이 존재한다면 두 포인터는 만날 것이다.
- 즉, 두 포인터가 동시에 같은 지점에서 만나는 것이다. 어디서 만나게 될까?왜 거기서 만나게 되는 걸까?

List 자료구조 접근법

일반적으로 주어지는 LinkedList의 형태

// LinkedList
class LinkedList {
    // 주어진 조건 singly-linked list    
    public class ListNode {
        int val;
        ListNode next;
        ListNode() { }
        ListNode(int val) {
            this.val = val;
        }
        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}

LinkedList의 Node 접근 방법

LinkedList 자료구조의 특성에 따라 head를 시작지점으로 포인터를 이용하여 순차적으로 노드에 접근

class LinkedList {
    public class ListNode {
        int val;
        ListNode next;
        ListNode() { }
        ListNode(int val) {
            this.val = val;
        }
        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    // LinkedList에서 Node에 접근 하는 방법
    public void accessNode(ListNode head) {
        ListNode cur = head;
        while (cur != null) {

            // 다음 노드 저장 
            cur = cur.next;
        }
    }
}

LinkedList의 Node 마지막에 추가하는 방법

class LinkedList {
    public class ListNode {
        int val;
        ListNode next;
        ListNode() { }
        ListNode(int val) {
            this.val = val;
        }
        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    private ListNode head;

    // List의 마지막에 Element 추가하는 방법
    public void addNode(ListNode e) {
        ListNode ptr = head;

        // ptr.next == null 이란 뜻은 tail 노드라는 것을 판단할 수 있음
        while (ptr.next != null) { // list의 마지막 노드까지 탐색
            ptr = ptr.next;
        }
        // next 값이 null 이므로 ptr 노드를 마지막 노드로 판단하여 next값에 list를 생성
        ptr.next = new ListNode(e, null);
    }
}

LinkedList의 Last Node 삭제하는 방법

class LinkedList {
    public class ListNode {
        int val;
        ListNode next;
        ListNode() { }
        ListNode(int val) {
            this.val = val;
        }
        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    private ListNode head;

    // ptr.next == null 이 tail 노드
    public void removeLast() {

        ListNode ptr = head; // 마지막 노드를 탐색하는 포인터 노드
        ListNode pre = head; // 마지막 노드 바로 전 노드를 저장할 노드

        while(ptr.next != null) {
            pre = ptr;  // 루프가 다 돌고나면 tail 노드 전 노드를 저장
            ptr = ptr.next;
        }

        pre.next = null; // tail 에 대한 포인터를 null 처리하여 removeLast 작업 
    }
}

LinkedList의 역순 정렬
tmp 노드를 생성하여 값을 변경하는 방식

cur.next -> next
prev -> cur.next
cur -> prev
next -> cur

class LinkedList {
    public class ListNode {
        int val;
        ListNode next;
        ListNode() { }
        ListNode(int val) {
            this.val = val;
        }
        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    private ListNode head;

    // 역순 정렬
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;

        while (curr != null) {
            ListNode nextTmp = curr.next; // 다음 노드를 next 노드에 저장
            curr.next = prev; // 이전 노드 (null)를 
            prev = curr;
            curr = nextTmp;
        }
        return prev;
    }
}

LinkedList의 Element 삭제

class LinkedList {
    public class ListNode {
        int val;
        ListNode next;
        ListNode() { }
        ListNode(int val) {
            this.val = val;
        }
        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    private ListNode head;

    public ListNode removeElement(ListNode e, int val) {
        ListNode sentinel = new ListNode(0); // 새 리스트를 저장할 노드를 생성
        sentinel.next = head;

        /*
            초기값 세팅 
            sentinel    sentinel.next
                        head            head.next
            prev        prev.next
                        curr            curr.next
         */
        ListNode prev = sentinel, curr = head; 

        while (curr != null) {
            if(curr.val == val) {
                prev.next = curr.next;
            } else {
                prev = curr;
            }
            // prev     curr    curr.next
            // ( )      ( )     ( )     모양을 유지
            curr = curr.next; 
        }

        // sentinal 다음 노드가 head로 저장되어 있어 next를 리턴
        return sentinel.next;
    }
}

Previous1.배열과문자열 Next3.스택과큐

Last updated 3 years ago

Was this helpful?