[자료구조] Linked List (1)

[C언어로 쉽게 풀어쓴 자료구조 / 천인국 / 생능출판]을 토대로 쓴 글입니다.

리스트(List)

: 차례대로 항목들을 나열하여 자료를 정리하는 방법

리스트의 항목은 순서 또는 위치를 갖는다

 

연산

- 삽입 연산: 리스트에 새로운 항목을 추가

- 삭제 연산: 리스트에서 항목을 삭제

- 탐색 연산: 리스트에서 특정한 항목 찾기

 

구현

배열? 가장 간단하게 리스트 구현할 수 있음, 순차적으로 메모리가 할당된다

- 장점: 구현이 간단하고 속도가 빠르다

- 단점: 리스트의 크기가 고정되는 점 -> 메모리 issue와 관련된다

 

연결 리스트

- 장점: 크기가 제한되지 않는다. 중간에서 쉽게 삽입, 삭제 가능하다

- 구현이 배열에 비해 복잡하다

=> 정리해야 할 자료가 많을 경우 연결 리스트를 사용하는 것이 유리하다

 

연결 리스트(Linked List)

출처 GeeksforGeeks

 

'줄로 연결된 상자'

 

여러 데이터가 줄을 통해 연결되어 있다. 첫 번째 데이터만 알 수 있으면 연결 리스트의 나머지 데이터들은 줄을 따라가면 얻을 수 있다.

데이터를 저장할 공간이 필요할 때 동적으로 공간을 만들어서 추가할 수 있다.

 

구조

상자를 노드(node)라고 표현한다. 노드는 위의 그림처럼 데이터 필드(data field), 링크 필드(link filed)로 구성되어 있다.

데이터 필드는 저장하고 싶은 데이터를, 링크 필드는 다른 노드를 가리키는 포인터가 저장된다.

마지막 노드의 링크 필드는 NULL이다. 이는 더 이상 연결된 노드가 없다는 것을 의미한다.

노드를 생성하기 위해서는 malloc을 이용한다.

 

정의 및 생성

 

노드의 정의이다. 

자기 참조 구조체(자기 자신을 참조하는 포인터를 포함하는 구조체)를 이용하여 정의한다. 

구조체 안에는 데이터를 저장하는 data 필드와 포인터가 저장되어 있는 link 필드가 존재한다.

 

 malloc 함수를 이용하여 노드의 크기만큼 동적 메모리를 할당 받는다.

노드가 생성되었다. 생성된 노드의 데이터 필드에는 10을, 링크 필드에는 NULL을 대입한다. 

 

이 때 한 개의 노드 p를 생성한 후 연결하려면?

head->link = p;

head의 링크 필드가 p를 가리킨다. 따라서 두 개의 노드가 존재하는 연결 리스트가 만들어졌다. 

이러한 방식을 통해 다른 노드를 더 생성하고 붙일 수 있다.

 

삽입 연산

출처 simplilearn

새로운 노드를 추가 할 때 삽입의 연산을 살펴보도록 하겠다. 만약 노드를 맨 앞이나 맨 뒤에 삽입한다면 비교적 간단하다.

두 노드의 사이에 새로운 노드를 삽입하는 경우를 살펴보겠다.

삽입하려는 노드의 앞에 위치한 노드를 선행 노드라고 하겠다.

 

1. 선행노드가 가리키고 있던 노드를 새로운 노드가 가리킨다

2. 선행 노드는 새로운 노드를 가리킨다

이 과정으로 두 노드 사이에 새로운 노드를 삽입 할 수 있다.

 

삭제 연산

출처 GeeksforGeeks

삽입의 반대 과정이다. 중간에 삭제하고 싶은 노드가 가리키고 있는 다음 노드를, 선행 노드가 가리키도록 하면 된다.

 

출력

연결리스트의 모든 노드를 출력하려고 한다. 노드의 마지막의 링크값은 NULL이다. 따라서 노드의 링크값이 NULL이 아니면 링크를 따라 방문하도록 하면된다. 이때 while문을 이용한다. 마지막 노드를 방문할시 데이터를 출력하고 종료한다.

검색 또한 같은 논리를 사용하여 모든 노드에 방문하여 탐색을 진행하면 된다.

 

+ PLUS

STL List

https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x04/list_example.cpp

basic-algo-lecture/0x04/list_example.cpp at master · encrypted-def/basic-algo-lecture

바킹독님의 알고리즘 강의 자료를 참고하여 STL List 사용법을 남기면

#include <bits/stdc++.h>
using namespace std;

int main(void) {
  list<int> L = {1,2}; // 1 2
  auto t = L.begin(); // t는 1을 가리키는 중
  L.push_front(10); // 10 1 2
  cout << *t << '\n'; // t가 가리키는 값 = 1을 출력
  L.push_back(5); // 10 1 2 5
  L.insert(t, 6); // t가 가리키는 곳 앞에 6을 삽입, 10 6 1 2 5
  t++; // t를 1칸 앞으로 전진, 현재 t가 가리키는 값은 2
  t = L.erase(t); // t가 가리키는 값을 제거, 그 다음 원소인 5의 위치를 반환
                  // 10 6 1 5, t가 가리키는 값은 5
                  
  cout << *t << '\n'; // 5
  for(auto i : L) cout << i << ' '; //auto를 활용한 출력
}

 

연결 리스트를 직접 구현하는 것보다 이렇게 쓰는 것이 훨씬 편한 것 같아 제대로 기억하고 활용해야겠다