[자료구조] Linked List

[자료구조] Linked List

정의

연결 리스트는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 자료구조입니다.

링크드 리스트의 예시

홈파티나 생일파티를 가면 뒤에 저런 배경을 해놓고 사진을 찍는 경우가 많습니다. 보통 벽에다가 걸어놓습니다.

저게 바로 링크드 리스트 즉 연결리스트입니다.

'생'이라는 데이터를 담고 있는 종이는 '일'이라는 데이터를 가리키고 있습니다.

즉 데이터를 담고 있는 노드들이 연결되어 있고, 노드의 포인터가 이전 노드와 다음 노드와의 연결을 담당합니다.

특징

연결리스트는 중간에 데이터를 추가하거나 삭제하더라도 전체의 인덱스가 한 칸씩 뒤로 밀리거나 당겨지지 않습니다. 그래서 array보다 데이터의 추가나 삭제가 용이합니다.

'일'을 없앤다면 '생'과 '축'이 연결되는 형식입니다.

하지만 인덱스가 없기때문에 특정 요소에 접근하는 것은 좀 느립니다.

그래서 보통 탐색 또는 정렬을 자주하는 경우엔 배열을 사용하고, 추가/삭제가 많은 경우엔 연결리스트를 사용합니다.

선언

LinkedList list = new LinkedList<>();

이렇게만 써주면 링크드 리스트 벌써 선언 다 한 것입니다.

예제

LinkedList list = new LinkedList()<>; list.addFirst(1); //맨 앞에다가 1을 넣음. list.addLast(1); //맨 뒤에다가 1을 넣음. list.add(3); //3 추가 list.add(1,100); //1번째 인덱스에 10을 넣음 list.removeFirst(); //가장 앞의 데이터 제거 list.removeLast(); //가장 뒤의 데이터 제거 list.remove(); //저 괄호에 아무것도 없으면 맨 앞 데이터 제거 list.remove(1); //인덱스 1 제거 list.clear(); //모든 값 제거 list.size(); //리스트의 크기 for(Integer i : list){ System.out.println(i); } // 리스트 전체 출력 Iterator iterator = list.iterator(); //iterator 선언 while(iter.hasNext()){ //다음 값이 있는지 체크함 System.out.println(iter.next()); } list.contains(1); //리스트에 1이 있는지 검색 list.indexOf(1); //1이 있는 index 반환

from http://soobinhand.tistory.com/31 by ccl(A) rewrite - 2021-10-27 00:26:24