순차 선형 리스트

배열이 순차 선형 리스트의 자료구조를 갖고 있다.

순차 선형 리스트는 원소의 위치에 대한 접근성이 쉽다는 장점이 있지만, 삽입, 삭제 후 원소들을 이동시키는 추가적인 작업과 시간이 필요하다는 단점이 있다.

만약 삽입 삭제 연산이 아주 많을 경우 원소들의 이동작업도 그와 비례하여 많아져 성능상의 문제를 일으킬 수 있다.

연결 리스트

순차 선형 리스트 방식의 연산 시간 문제와 오버헤드 문제를 개선한 자료 표현 방식이다.
연결 리스트는 각 원소에 저장된 주소에 대한 참조에 의해 연결되는 방식이기 때문에, 순서를 맞추기 위한 오버헤드도 발생하지 않는다.

구조

원소는 연결될 다음 원소에 대한 주소를 저장해야 하므로 <원소,주소> 단위로 저장해야 한다. 여기서 쓰이는 단위구조를 노드라고 한다. 노드는 데이터 필드와 다음 노드의 주소를 저장하는 링크 필드로 구성된다.

연산

노드 추가

Add

1. head가 null일 때

노드를 생성해서 head에 넣어주면 된다.

1. head가 null이 아닐 때

head가 가리키는 다음 노드의 참조값이 null이 될 때까지 탐색해 마지막 노드 참조값에 새 노드값을 대입해준다.

첫 노드에 삽입

insertFirstNode

중간 노드 삽입

insertMiddleNode

마지막 노드 삭제

remove

중간 노드 삭제

delete

이전 노드가 null이 아닌 경우

해당 노드를 삭제하고 전 노드의 링크가 다음 노드를 가리키도록 변경해준다.

관련문제

🔆 D-5

• [leetCode] 19. Remove Nth Node From End of List
• [leetCode] 876. Middle of the Linked List

Reference

• https://taesung1993.tistory.com/10
• https://ppomelo.tistory.com/38