선형 자료구조 - 연결 리스트(Linked List)

연결 리스트(Linked List)

-원소들을 저장할 때 그 다음 원소가 있는 위치를 포함하는 방식으로 저장하는 자료구조

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

 

 

연결 리스트의 장점

-데이터 공간을 미리 할당할 필요 없음

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

 

 

연결 리스트의 단점

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

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

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

 

 

연결 리스트의 기본 구조

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

이름처럼 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 됨

 

노드(Node)

-데이터 저장 단위로, 값과 포인터로 구성

 

포인터(Pointer)

-다음 노드나 이전 노드의 연결 정보(링크 연결 작업하는 부분을 의미함)

단방향 연결리스트

 

** 각 박스의 data는 노드를 의미, next는 포인터를 의미

** 가장 처음에 위치하는 노드를 일반적으로 head, 가장 끝에 있는 노드를 tail이라고 함

 

 

연결 리스트의 기본 연산

• 데이터 추가
  • 데이터 추가 위치(head, 중간, tail)에 따른 연결 작업 필요

데이터 가장 앞에 추가

1. 추가할 데이터를 담을 새로운 노드 생성

2. 링크 연결 작업

3. head 이전 작업

 

 

데이터 가장 끝에 추가

1. 추가할 데이터를 담을 새로운 노드 생성

2. head로부터 끝 노드까지 순회

3. 링크 연결 작업

 

 

데이터 중간에 추가

1. 추가할 데이터를 담을 새로운 노드 생성

2. head로부터 데이터 추가 위치 직전 노드까지 순회

3. 링크 연결 작업 (링크 정보가 유실되지 않게 주의해야 함)

 

 

• 데이터 삭제
  • 데이터 삭제 위치(head, 중간, tail)에 따른 연결 작업 필요

가장 앞 데이터 삭제

1. 삭제 대상 노드 지정(별도의 변수로 지정 ex. delete_node)

2. head 이전 작업 

3. delete_node 삭제

 

** Java의 경우 garbage collection이라는 기능이 있는데 더 이상 해당하지 않는 메모리를 자동으로 지워줌

 

 

가장 끝 데이터 삭제

1. head로부터 가장 끝까지 순회

2. 끝 노드 삭제

3. 삭제 이전 노드의 링크 처리

 

 

중간 데이터 삭제

1. head로부터 삭제 대상 노드까지 순회 및 해당 노드 지정(delete_node)

2. 삭제 대상 이전/이후 노드의 링크 연결 작업

3. delete_node 삭제