LinkedList

2021-01-12 15:22

LinkedList

컴퓨터에 자료를 저장하는 구조의 한 종류.
일렬로 연결된 데이터를 저장할 때 사용한다. 연속적이지 않게 존재하는 데이터를 서로 연결한 형태로 구성되어있는 것이 특징이다.
- 배열과 LinkedList:
LinkedList의 각 요소들을 node라고 부르며, 각 node들은, 다음 node에 대한 참조(주소값)와 저장하고 있는 데이터로 구성된다.
```
class Node {
  Node next;	// 다음 요소의 주소를 저장
  Object obj; // 데이터를 저장
}
```
참조값을 변경하면 되므로, 추가와 삭제의 속도가 굉장히 빠르지만, 원하는 값을 찾는 경우 각 요소들이 모두 연결 되어 있어, 순차적으로 데이터를 확인해야 하기 때문에 속도가 느리다.
추가
삭제

배열과의 비교:

컬렉션	접근 시간	추가 / 삭제	비고
Array	빠르다	느리다	순차적인 추가삭제는 더 빠름. 비효율적인 메모리를 사용한다.
LinkedList	느리다	빠르다	데이터가 많을수록 접근성이 떨어진다는 단점이 있다.

대표적인 비교 요소는 위와 같은 것이 있다.

다만 장점과 단점이 명확하지 않아, 추가적으로 설명을 하자면
- 배열:
  1. 장점:
    - 구조가 간단하며, 사용하기가 쉽다.
    - 데이터 검색 시, 접근 시간이 가장 빠르다는 장점을 가짐.
  2. 단점:
    - 크기를 변경하지 못해, 더 큰 배열을 가지고 싶다면 새로운 배열을 생성해, 데이터를 복사해야한다.
    - 실행 속도 향상을 위해 처음부터 큰 배열을 생성하게 될 경우, 메모리가 낭비 된다.
    - 배열의 순차적인 추가 삭제는 빠를지 모르지만, 중간에 데이터를 추가하고 싶은 경우 소요되는 시간이 많다.
- LinkedList:
  1. 장점:
    - 다음 노드를 참조하는 특성 때문에 데이터의 추가와 삭제가 빠르게 이루어진다.
    - 배열처럼 사이즈를 지정해서 사용하지 않기 때문에 보다 탄력적으로 사용할 수 있다.
  2. 단점:
    - 다음 노드를 참조하는 특성 때문에 검색에 시간이 많이 소요된다.

위와 같은 장단점 중, 검색에 초점을 두어 코드로 비교하자면 아래와 같다.

조건: 3번째 index에 위치한 값을 얻고 싶다.

배열의 경우:

int[] arr = {0,1,2,3,4,5};
      
int a = arr[3];

LinkedList의 경우:

Node serchNode(int index){
  Node tmpNode = head;
   for (int i = 0; i < index; i++) {
        tmpNode = tmpNode.next;
      }
  return tmpNode;
}
      
...
public static void main(String[] args){
...
  serchNode(3);
}

위와 같이 LinkedList는 원하는 값을 찾기 위하여 반복문을 돌아야 한다는 특징을 가진다.

Study Blog

LinkedList