연결 리스트(Linked List)

연결 리스트(Linked List) : 데이터 요소들이 노드(Node)들에 의해 연결된 자료 구조입니다.

- 데이터를 링크로 연결해서 관리하는 자료구조입니다.

- 자료의 순서는 정해져 있지만, 메모리상 연속성이 보장되지는 않습니다.

 

 

연결 리스트(Linked List) 기본 구조

Linked List의 기본 구조

 

노드(Node) : 데이터 저장 단위로, 값(Data)과 포인터(Link)로 구성되어있습니다.

포인터(Pointer) or Next or Link : 다음 노드나 이전 노드의 연결 정보

Head Structure

 

Data Node Structure

연결 리스트(Linked List)의 장점

- 데이터 공간을 미리 할당할 필요가 없습니다.

- 즉, 리스트의 길이가 가변적이라 데이터 추가/삭제가 용이합니다.

 

연결 리스트(Linked List)의 단점

- 연결구조를 위한 별도 데이터 공간이 필요합니다.

- 연결 정보를 찾는 시간이 필요합니다.(접근 속도가 상대적으로 느립니다.)

- 데이터 추가, 데이터 삭제 시 앞뒤 데이터의 연결을 재구성하는 작업이 필요합니다.

 

 

데이터 추가(Insert Node)

데이터 추가 위치(Head, 중간, tail)에 따른 연결 작업이 필요합니다.

 

Empty List에 추가하는 경우

Before Add

After Add

1. 새 노드에 메모리를 할당하고 데이터를 노드로 이동합니다.

2. Head 노드가 새 노드를 가리킵니다.

 

Head에 추가하는 경우

Before Add

After Add

1. 새 노드에 메모리를 할당하고 데이터를 노드로 이동합니다.

2. 새 노드가 후속 노드를 가리킵니다.

3. Head 노드가 새 노드를 가리킵니다.

 

Middle에 추가하는 경우

Before Add

 

After Add

1. 새 노드에 메모리를 할당하고 데이터를 노드로 이동합니다.

2. Head 노드로부터 데이터 추가 위치 직전 노드까지 순회합니다.

3. 데이터 추가 위치 직전 노드가 새 노드를 가리킵니다.

4. 새 노드가 데이터 추가 위치 이후 노드를 가리킵니다.

 

Tail에 추가하는 경우

Before Add

After Add

1. 새 노드에 메모리를 할당하고 데이터를 노드로 이동합니다.

2. Head 노드로부터 마지막(Tail) 노드까지 순회합니다.

3. 마지막(Tail) 노드가 새 노드를 가리킵니다.

 

 

 

데이터 삭제(Delete Node)

데이터 삭제 위치(Head, 중간, Tail)에 따른 연결 작업이 필요합니다.

 

 

Head Node 삭제하는 경우

Befor Delete

After Delete

1. 삭제할 노드를 지정합니다.(Delete_Node)

2. Head를 다음 노드로 변경합니다.

3. Delete_Node를 삭제합니다.

 

Middle Node 삭제하는 경우

Before Delete

After Delete

 

1. Head로 부터 삭제 대상 노드까지 순회 및 해당 노드를 지정합니다.(Delete_Node)

2. 삭제 대상 이전/이후 노드의 링크 연결 작업을 진행합니다.

3. Delete_Node를 삭제합니다.

 

Tail 노드 삭제하는 경우

Before Delete

After Delete

1. Head로 부터 가장 마지막까지 순회합니다.

2. 끝 노드를 삭제합니다.

3. 삭제 이전 노드의 링크를 처리합니다.

 

 

 

 

 

List 메소드

list.add("data") : data을 추가합니다.

list.add(1, "data") : 1번 index에 data를 추가합니다.

list.addFirst("data") : 제일 앞에 data를 추가합니다.

list.addLast("data") : 마지막에 data를 추가합니다.

list.remove() : 첫 번째 값을 제거합니다.

list.remove(n) : n index자리의 값을 제거합니다.

list.removeFirst() : 제일 앞에있는 값을 제거합니다.

list.removeLast() : 마지막에 있는 값을 제거합니다.

list.clear() : 리스트에 있는 모든 값을 제거합니다.

list.get(n) : n index에 있는 값을 반환합니다.

 

 

 

시간 복잡도(Time Complexity)

삽입(Insertion) = 삽입의 위치가 제일 앞인 경우 : O(1), 삽입의 위치가 나머지인 경우 : O(n)

삭제(Deletion) = 삭제의 위치가 제일 앞인 경우 : O(1), 삭제의 위치가 나머지인 경우 : O(n)

검색(Search) = O(n)

 

 

 

 

 

 

References

- Chapter 5. General Linear Lists, Data Structures: A Pseudocode Approach with C, Second Edition, Richard F. Gilberg Behrouz A. Forouzan.