1. 연결 리스트 (Linked List) & 배열 (Array)

본 게시글은 책 : 면접을 위한 CS 전공지식 노트 (출판사 : 길벗, 주홍철 지음) 을 참조하여 작성하였습니다. + 구글링

---

*선형 자료 구조 : 요소가 일렬로 나열되있는 자료구조

 

◆  연결 리스트 (Linked List)

- 연결리스트는 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화 시킨 자료구조

- head 노드 에서 시작되어 tail 노드로 끝나는 구조

- 삽입과 삭제에 O(1), 탐색에는 O(n) 소요

- 싱글 연결 리스트 (Single Linked List)는 노드가 한방향으로 연결되어 있는 연결리스트

     : next포인터로 다음 노드로 연결

ex)

struct ListNode {
	int nData;
    ListNode* next;

}


int main(){

     ListNode* FirstNode;
     FirstNode->nData = 4;
     
     ListNode* SecondNode;
     SecondNode->nData = 5;
     
     SecondNode = FirstNode->next;
     
     cout << FirstNode->next << endl; // 5출력

     return 0;
}

 

- 이중 연결 리스트 (double Linked List)는 노드가 양방향으로 연결되어 있는 연결리스트

    : next포인터로 다음 노드, prev로 이전 노드 연결

struct ListNode {
	int nData;
    ListNode* next;
    ListNode* prev;

}


int main(){

     ListNode* FirstNode;
     FirstNode->nData = 4;
     
     ListNode* SecondNode;
     SecondNode->nData = 5;
     
     FirstNode = SecondNode->prev;
     SecondNode = FirstNode->next;
     
     ListNode* ThirdNode;
     ThirdNode->nData = 6;
     
     SecondNode = ThirdNode->prev;
     ThirdNode = SecondNode->next;
     
     cout << FirstNode->next << endl; // 5출력
     cout << ThirdNode->prev << endl; // 5출력

     return 0;
}

- 원형 이중 연결 리스트 (circular linked list) : 이중 연결리스트와 같지만 마지막 노드의  next 포인터가 헤드 노드를 가리킴

---

◆  배열 (Array)

- 연배열은 같은 타입의 변수들로 이루어져 있고, 크기가 정해져 있으며, 인접한 메모리 위치에 있는 데이터를 모아놓은 집합

- 중복을 허용하고 순서 존재

- 탐색에 O(1)이 되어 랜덤접근 (Random access)이 가능

- 삽입과 삭제에는 O(n) 소요

- 데이터 추가와 삭제를 많이 하는 것은 연결 리스트, 탐색을 많이 하는 것은 배열로 하는 것이 유용

- 직접 접근이라고 하는 랜덤 접근은 동일한 시간에 배열과 같은 순차적인 데이터가 있을 때 임의의 인덱스에 해당하는 데이터에 접근할 수 있는 기능

- 데이터를 저장된 순서대로 검색해야 하는 순차적 접근과는 반대

- 배열 vs 연결 리스트

    : 연결 리스트에서의 삽입 삭제는 노드 연결을 끊거나 이으면 끝

    : 배열은 삽입, 삭제의 경우 공간 재배치 필요로 링크드 리스트에 비해 비효율적

    : 연결 리스트에서의 탐색은 순서를 알고 있어도 head에서 부터 많은 양의 이동이 필요

    : 배열의 순서를 알고있다면 해당 순서로 바로 탐색 가능

ex )

struct ListNode {
	int nData;
    ListNode* next;
    ListNode* prev;

}

using namespace std;

int main(){

	// 배열
    int arr[100];
    arr[0] = 4;
    arr[1] = 5;
    arr[2] = 6;
	 
	// 링크드 리스트
     ListNode* FirstNode;
     FirstNode->nData = 4;
     
     ListNode* SecondNode;
     SecondNode->nData = 5;
     
     
     FirstNode = SecondNode->prev;
     SecondNode = FirstNode->next;
     
     ListNode* ThirdNode;
     ThirdNode->nData = 6;
     
     SecondNode = ThirdNode->prev;
     ThirdNode = SecondNode->next;
     
     // 링크드 리스트에서의 데이터 추가
     
     ListNode* RandomNode;
     RandomNode->nData = 7;
     
     FirstNode = RandomNode->prev;
     ThridNode = RandomNode->next;
     
     // 배열에서의 데이터 추가
     int nTemp = 7;
     arr[3] = arr[2];
     arr[2] = arr[1];
     arr[1] = nTemp;
     
     // 링크드 리스트에서 데이터 6 찾기
     ListNode* TempNode = FirstNode;
     while(TempNode->Data != 6) {
     	TempNode = TempNode->next;
     }
     
     cout << TempNode->Data << endl;
     
     // 배열에서 데이터 6찾기
     for(int i =0; i < 4; i++) {
     	if(arr[i] == 6)
        	cout << arr[i] << endl;
	}
     return 0;
}

---

 Linked List 릿코드의 추억.. 

 위의 글과 관련하여 추가적인 내용이나 피드백은 언제나 환영입니다 :)