[Data Structure 기초] Linked List

 

Linked List (연결 리스트)

- 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조.
- 데이터를 담고 있는 노드들이 연결되어있는데, 노드의 포인터가 이전이나 다음의 노드와의 연결을 담당하게 된다.

 

- 키와 값은 모두 객체이다. 값은 중복 저장될 수 있지만 키는 중복 저장될 수 없다. 

- 만약 기존에 저장된 키와 동일한 키로 값을 저장하면 기존의 값은 없어지고 새로운 값으로 대치된다.

- 실제 데이터를 저장시킬 때는 Node 타입의 배열에 저장된다. HashMap에 선언된 Node 타입 변수 및 클래스이다.

Hashmap 시간복잡도

접근, 탐색 :  O(n)

추가 , 삭제  : O(1)

 

연산
void addFirst(Object obj)	맨 앞에 객체(obj)를 추가
void addLast(Objec obj)	맨 뒤에 객체(obj)를 추가
boolean add(Object obj)	마지막에 객체를 추가(성공하면 true)
void add(int index, Object element)	지정된 위치(index)에 객체를 저장
void addAll(Collection c)	주어진 컬렉션의 모든 객체를 저장(마지막에 추가)
void addAll(int index, Collection c)	지정한 위치부터 주어진 컬렉션의 데이터를 저장한다.

 

//연결리스트 사용예제
LinkedList list1 = new LinkedList();
list1.add("1");
list1.add("2");

// list1안에 "1" 값이 있는지 확인
list1.contains("1"); // true


LinkedList list2 = new LinkedList();
list2.add("1");
list2.add("2");
 
// list1에 list2의 모든 노드가 포함되어 있는지 확인
list1.containsAll(list2); // true

 

장점

- 자료의 삽입과 삭제가 용이
-  리스트 내에서 자료의 이동이 불필요
-  사용 후 기억 장소의 재사용이 가능

단점

-  포인터의 사용으로 인해 저장 공간의 낭비
-  알고리즘이 복잡
-  특정 자료의 탐색 시간이 많이 소요

 

 

 

 

관련 link

https://hyeinisfree.tistory.com/64

[Data Structure] 연결 리스트(Linked List)

https://inpa.tistory.com/entry/JAVA-%E2%98%95-LinkedList-%EA%B5%AC%EC%A1%B0-%EC%82%AC%EC%9A%A9%EB%B2%95-%EC%99%84%EB%B2%BD-%EC%A0%95%EB%B3%B5%ED%95%98%EA%B8%B0

🧱 자바 LinkedList 구조 & 사용법 - 정복하기