Linked List

 

자료구조 :  컴퓨터에 자료를 저장하는 구조

Linked List

- 일렬로 연결된 데이터를 저장할 때 사용

- 데이터를 저장할 수 있는 공간이 있으면, 그 안에 다음 데이터의 주소를 가지고 있는 구조 

 

배열과 비교하자면,

배열 방 크기는 한 번 저장하면 늘이거나 줄일 수 없다.

즉, 길이가 정해져있지않은 데이터를 다루려고할 때에는 Linked List가 적절

 

데이터를 삽입하려고 하면, 

앞의 노드가 가리키던 주소를 자신이 가진다.

그리고 앞의 노드는 자신의(삽입 노드) 주소를 가리키게 한다.

삭제하는 경우에는 삭제하려면,

삭제되는 노드가 가리키던 next노드의 주소값을

삭제 노드 앞의 노드가 가져간다.

이때 노드는 자신을 가리키는 주소가 사라졌을 뿐

여전히 데이터를 가지고 있는 상태!

 

Java에서는 이 노드가 차지하는 메모리를 자동으로 삭제해주지만

C,C++에서는 직접 삭제해야한다.

 

단방향/양방향 Linked List 개념

단방향: 각 노드가 자신 다음 노드의 주소만을 가지고 있다.

한쪽으로만 가기 때문에 헤더 주소 하나만 포인터를 저장하고 있다. 

 

양방향: 각 노드가 자신 다음 뿐만 아니라 앞의 노드의 주소를 가지고 있다.

양쪽끝에 포인터를 저장하고 있어 맨 끝의 데이터로 가야할 때 효율적이다. 

 

근데..

공간의 효율성을 중요하게 생각하는 경우,굳이 양방향 Linked List 사용할 필요는 없다.

 

 

 

 

알고리즘 문제

정렬되어 있지 않은 Linked List 에서 중복값을 삭제하시오. 

(단, 별도의 buffer를 사용하지 않고)

 

n과 r이라는 포인터를 두 개 생성한다.
n은 노드의 값을 가지고 있고,
r은 그 노드 다음의 노드들을 한 번씩 돌아다니면서 중복되는 값을 찾아 삭제한다.