연결 리스트

1. 개념:
   • 등장배경:
     • 순차 선형 리스트(배열)는 논리적인 순서와 물리적인 순서가 같기 때문에 원소의 위치를 찾아 액세스하기 쉽다는 장점이 있지만, 삽입 연산이나 삭제 연산에 원소들을 이동시키는 추가적인 작업과 시간이 필요함
     • 원소의 개수가 많고, 삽입, 삭제 연산이 많이 발생하는 경우에는 원소들의 이동 작업으로 인한 오버헤드가 증가, 결국, 메모리 사용의 비효율성의 문제를 갖음.
   • 단위:
     • 노드: 연결 자료구조 방식에서 원소는 연결될 다음 원소에 대한 주소를 저장해야 하기 때문에, <원소, 주소> 단위로 저장
       • 원소의 값을 저장하는 데이터 필드(Data Field)
       • 다음 노드의 주소를 저장하는 링크 필드(Link Field)

2. 종류:

   • 단순 연결 리스트:
     • 노드가 하나의 링크 필드에 의해서 다음 노드와 연결되는 구조를 가진 연결 리스트
     • 데이터의 삽입: 노드 중간에 삽입될 경우, 1. 이전노드의 다음노드 주소를 받고 2. 이전노드에 삽입되는 노드의 주소를 전달한다
   • 원형 연결 리스트
     • 장점: 하나의 노드에서 모든 다른 노드로의 접근 가능
     • head 를 두어 시작 노드와 끝 노드를 정의해야 한다
     • 특정 노드를 검색할 때 만일 그 노드가 연결 리스트에 포함되어 있지 않은 노드라면, 무한 루프(loop)에 빠질 가능성 있어, 검색을 끝낼 수 있는 노드를 지정해 두는 것이 좋음
   • 이중 연결 리스트
     • 노드가 두개의 링크 필드를 가지고 있어, 이전 노드와 다음 노드의 정보를 가지고 있다
     • 장점: 양방향 탐색
     • 단점: 변수(링크 필드)를 하나 더 사용 == 메모리를 더 많이 사용한다는 의미
     • 현실에서 사용하는 연결 리스트는 대부분 이중 연결 리스트
   • 이중 원형 연결 리스트

3. 비교 리스트 종류 간 비교

   • 배열 과 연결리스트:
     • 배열은 할당받은 메모리 내 에서 동작
     • 연결리스트는 동적으로 메모리 할당 후 동작, 메모리 주소에 대한 참조를 하기 때문에 추가 메모리 사용
   • 단순 연결 리스트 VS 이중 연결 리스트
     • 데이터 검색, 삭제 성능: 단순 연결 리스트 < 이중 연결 리스트
     • 메모리 추가 사용: 단순 연결 리스트 < 이중 연결 리스트
   • 이중 연결 리스트 VS 원형 연결 리스트
     • 구조가 유사
     • 데이터 삽입 시, 이중 연결 리스트의 경우 마지막 노드를 찾는데 O(N) 이 소요되나 원형 연결 리스트의 경우 시작 노드에서 마지막 노드 를 바로 찾을 수 있다

4. JAVA 의 Vector, ArrayList, LinkedList 차이

   • 차이
   • Vector:
     • 구버젼 호환용
     • 동기화 처리가 내부적으로 일어남으로 다른 객체보다 무겁다 == 성능 저하
   • ArrayList:
     • 배열의 복사에 의한 데이터 저장처리를 내부적으로 행한다
     • 각 데이터에 대한 인덱스를 가지고 있기때문에 검색이 매우 빠르다
     • 많은 데이터의 추가 / 삭제시에는 배열의 복사가 빈번하게 일어나, 성능이 떨어지는 단점이 있다
   • LinkedList:
     • 다음 자료의 위치정보를 가지며, 내부적인 인덱스는 가지고 있지 않다
     • 데이터의 추가 / 삭제는 위치정보의 수정만으로 가능하기 때문에 많은 정보의 추가 / 삭제처리가 필요할때 유용하다
     • 데이터가 많은 경우의 검색시 처음 자료로부터 순차적으로 찾아 나가야 하기 때문에 느려지는 단점이 있다
   • 데이터 추가 / 삭제: ArrayList < LinkedList
   • 데이터 검색: ArrayList > LinkedList