📌 서론.

연결리스트에 대해 배웠다.

연결리스트의 성질

• 연결리스트는 k번째 원소를 찾기 위해 O(k) 시간이 필요.
• 임의의 위치에 원소를 추가/임의 위치의 원소 제거는 O(1)
• 원소들이 메모리 상에 연속해있지 않아 Cache hit rate가 낮음. 대신 할당이 다소 쉬움.

정적배열, 동적배열, 연결리스트

연산	정적 배열	동적 배열	연결 리스트
임의 위치에 원소 확인/변경	O(1)	O(1)	O(n)
임의 위치에 원소 추가/제거	O(n)	O(n)	O(1)
마지막에 값 삽입/삭제	O(n)	O(1)	O(1)

자바의 연결리스트 LinkedList

Java에서 LinkedList를 사용하는 방법:

1. 선언

LinkedList<String> lnkList = new LinkedList<>();

1. 데이터 추가 (시간복잡도: O(1))

   lnkList.add("유재석");
   lnkList.add("조세호");
   lnkList.add("박명수");
   

   1. 초기값, 마지막값 추가

      lnkList.addFirst("서장훈");
      lnkList.addLast("김희철");
      

   2. 임의 위치에 추가 (시간복잡도: O(1))

      list.add(1, "김영철"); // index = 1 앞에 추가.
      

2. 데이터 삭제 (시간복잡도: O(1))

   lnkList.remove(4); // index = 4 에 해당하는 값을 삭제.
   lnkList.removeFirst();
   lnkList.removeLast();
   

3. 임의 인덱스의 데이터 변경 (시간복잡도: O(n))

   lnkList.set(3, "이수근"); //index = 3 의 데이터 변경
   

4. 데이터 조회

   System.out.println(lnkList.get(1)); // 임의 인덱스 조회 : 시간복잡도 O(n)
   System.out.println(lnkList.getFirst()); // 첫번째 인덱스 조회 : 시간복잡도 O(1)
   System.out.println(lnkList.getLast()); // 마지막 인덱스 조회 : 시간복잡도 O(1)
   

5. 데이터 전체 삭제

   list.clear();
   if(list.isEmpty()){
     System.out.println("리스트 요소 개수 : " + lnkList.size());
   }
   

6. 정렬

   Collections.sort(lnkList);
   

연결리스트와 동적 배열의 차이.

[Section 2] 동적 배열과 연결 리스트(Linked List)의 이해

[Java] 자바 리스트(ArrayList, LinkedList) 삽입 삭제 수행시간 비교 정리