[Coding Interview University] 링크드 리스트 : 이론 및 구현

<본 블로그는 코딩인터뷰대학 님의 Git과 서적을 참고해서 공부하며 작성하였습니다 :-)>

 

🫧 연결 리스트

: 차례로 연결된 노드를 표현해주는 자료구조

: 단) 배열과 달리 특정 인덱스를 상수 시간에 접근할 수 없다

(k번째 원소를 찾고싶다면 처음부터 k번 루프 돌아야함)

: 장) 리스트의 시작 지점에서 아이템을 추가하거나 삭제 연산을 상수 시간에 할 수 있다

 

단방향 (좌) 양방향 (우)

• 단방향  
  • 각 노드는 다음 노드 가리킴
• 양방향
  • 각 노드는 다음 노드와 이전 노드를 함께 가리킴

 

💖 (단방향) 연결 리스트 만들기

class Node {
	Node next = null;
	int data;
	public Node(int d) {
		data = d;
	}

	void appendToTail(int d) {
		Node end = new Node(d);
		Node n = this;
		while (n.next != null) {
			n = n.next;
		{
		n.next = end;
	}
}

 

💖 (단방향) 연결 리스트 삭제하기

1. 노드 n 이 주어지면, 이전 노드 prev 를 찾아 prev.next 와 n.next 가 같도록 설정한다

• 양방향 연결 리스트일 경우, n.next가 가리키는 노드를 갱신하여 n.next.prev 가 n.prev 가 같도록 설정

💥 주의
- 널 포인트 검사를 반드시 한다
- head와 tail 포인터를 갱신한다

Node deleteNode(Node head, int d) {
	Node n = head;
	if (n.data == d) {
		return head.next;    // head 움직이기
	}

	while (n.next != null) {
		if (n.next.data == d) {
			n.next = n.next.next;
			return head;     // head 움직이지 않음
		}
	}
	return head;
}
	

 

💖 Runner (부가 포인터)

: 연결리스트를 순회할 때 두 개의 포인터를 동시에 사용하는 것

: 한 포인터가 다른 포인터보다 앞서도록 한다

• 앞선 포인터는 뒤 포인터보다 항상 지정된 개수만큼은 앞설 수 있다
• 뒤 포인터를 여러 노드를 한번에 뛰어넘도록 설정할 수 있다

 

💖 재귀 문제

: 재귀 호출 깊이가 n일 경우, 해당 재귀 알고리즘이 적어도 O(n) 의 공간을 사용

 

🫧 링크드 리스트 구현하기

➡️ size() - 리스트 안의 데이터 개수를 반환한다.

LinkedList<Integer> list = new LinkedList<Integer>(Arrays.asList(1,2,3));
System.out.println(list.size()); //list 크기 : 3

➡️ empty() - 리스트가 비어있다면 true를 반환한다.

// 리스트가 비었는가
template <typename E>
bool SLinkedList<E>::empty() const{
    return head == NULL;
}

➡️ value_at(index) - index번째 위치의 value을 반환한다. (가장 앞은 0부터 시작한다.)

# declaring array
a = [18, 22, 33, nil, 5, 6]

puts "values_at() method form : #{a.values_at(2, 4)}\\n\\n"
// values_at() method form : [33, 5]

➡️ push_front(value) - 가장 앞에 value를 추가한다.

int main(void) {
	list<int> L = { 3, 7 };
	L.push_front(1); // { 1, 3, 7 }
	return 0;
}

➡️ pop_front() - 가장 앞에 있는 것을 제거하고, 그 value를 반환한다.

int main(void) {
	list<int> L = { 1, 5, 3, 7, 10 }   
	L.pop_front(); // { 5, 3, 7, 10 }
	return 0;
}

➡️ push_back(value) - 가장 끝에 value을 추가한다.

int main(void) {
	list<int> L = { 3, 7 };
	L.push_back(10); // { 3, 7, 10 }
	return 0;
}

➡️ pop_back() - 가장 끝에 있는 것을 제거하고, 그 value를 반환한다.

int main(void) {
	list<int> L = { 1, 5, 3, 7, 10 }   
	L.pop_back(); // { 5, 3, 7, 10}
	return 0;
}

➡️ front() - 가장 앞에 있는 것의 value를 가져온다.

class CircleList{
public:
    CircleList(); // 생성자
    ~CircleList(); // 소멸자

    const string& front() const; // 커서 다음의 원소
};

➡️ back() - 가장 끝에 있는 것의 value를 가져온다.

class CircleList{
public:
    CircleList(); // 생성자
    ~CircleList(); // 소멸자

    const string& back() const; // 커서의 원소

};

➡️ insert(index, value) - index번째 위치에 value를 추가한다. 즉, index번째에 새로 추가된 것이 기존의 index번째에 있던 것을 가리킨다.

list<int>::iterator iterInsertPos = list1.begin();
list1.insert(iterInsertsPos, 100);    // 첫 번째 위치에 100 넣기

➡️ erase(index) - index번째에 있는 노드를 삭제한다.

list1.erase(list1.begin());    // list1 첫 번 째 요소 삭제

➡️ value_n_from_end(n) - 뒤에서부터 n번째에 있는 노드의 value를 반환한다.

➡️ reverse() - 리스트를 뒤집는다.

public class UnitTest {
    public static void main(String[] args) {
        SinglyLinkedList list = new SinglyLinkedList();
        list.addLast(1);
        list.addLast(2);
        list.addLast(3);
        list.addLast(4);

        System.out.println(list);
        list.reverse();

        System.out.println(list);
    }
}

// 1 -> 2 -> 3 -> 4
// 4 -> 3 -> 2 -> 1

➡️ remove_value(value) - value와 같은 값을 가지는 첫 번째 노드를 제거한다.