📒 갈무리 - 연결리스트

📌 연결리스트란?

- 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조이다.

- 각 노드의 포인터가 다음 또는 이전의 노드와의 연결을 담당한다.

 

📌 ArrayList

- ArrayList는 배열의 형태로 되어있다.

- 각각의 저장 공간을 '엘리먼트'라고 한다.

- 데이터의 추가와 삭제하는 속도가 느리다. O(n)

- 데이터의 검색이 빠르다. O(1)

 

📌 단순 연결 리스트(Singly Linked List)

- LinkedList는 '링크 포인터'라는 것으로 데이터를 연결하고 있다.

- 저장 공간 하나하나를 '노드'라고 한다.

- 각 노드는 다음 노드의 링크 포인터(다음 노드의 위치)와 데이터를 가지고 있다.

- head 데이터 : 첫 번째 데이터의 링크 포인터를 가지고 있다.

- head부터 데이터를 추가할 때마다 노드를 추가하여 데이터를 저장한다.

- 데이터의 추가와 삭제가 빠르다. O(1)

- 데이터의 검색이 느리다. O(n)

- 단방향 탐색이다.(앞에 있는 노드는 뒤에 있는 노드를 알 수 있지만 뒤에 있는 노드는 앞에 있는 노드를 알 수 없다.)

- 마지막 데이터의 링크 포인터는 null 값이다.

- 어떠한 타입도 될 수 있다.

 

📌 이중 연결 리스트(Doubly Linked List)

- 단순 연결 리스트의 탐색 기능을 개선한 리스트 자료구조

- 한 노드에 링크 포인터가 두 개가 존재하고, 각각의 포인터는 앞의 노드와 뒤의 노드를 가리킨다.

- 양방향 탐색이 가능하다.

- 포인터를 두 개 가지고 있기 때문에 크기가 크다.

- C#에서 제공하는 LinkedList는 이중 연결 리스트이다.

// C#
            LinkedList<int> number = new LinkedList<int>(); // 선언

            // 초기화
            number.AddFirst(10); // 10
            number.AddLast(15); // 10 15
            number.AddFirst(3); // 3 10 15
            number.AddLast(20); // 3 10 15 20

            // 노드 찾기
            LinkedListNode<int> nodeTemp = number.Find(10);

            // 노드 삽입
            number.AddAfter(nodeTemp, 2); // nodeTemp의 뒤로 들어감
            // 3 10 2 15 20

            number.AddBefore(nodeTemp, 1); // nodeTemp의 앞으로 들어감
            // 3 1 10 2 15 20

            number.Remove(10); // 값 10을 삭제
            // 3 1 2 15 20

 

📌 원형 연결리스트(Doubly Circular Linked List)

- 이중 연결리스트와 동일한 구조에 더해, 처음과 마지막 노드가 서로 연결되어 있다.

- 첫번째 노드의 이전 노드는 마지막 노드를 가리키고 있다.

- 마지막 노드의 다음 노드는 첫 번째 노드를 가리키고 있다.

 

💡 TIP

자료구조들을 직접 구현해서 사용하는 연습을 해보며 구조에 익숙해져 보자.