[자료구조] Linked List

정의

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

 

링크드 리스트의 예시

 

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

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

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

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

 

특징

• 연결리스트는 중간에 데이터를 추가하거나 삭제하더라도 전체의 인덱스가 한 칸씩 뒤로 밀리거나 당겨지지 않습니다.
• 그래서 array보다 데이터의 추가나 삭제가 용이합니다.
• '일'을 없앤다면 '생'과 '축'이 연결되는 형식입니다.
• 하지만 인덱스가 없기때문에 특정 요소에 접근하는 것은 좀 느립니다.
• 그래서 보통 탐색 또는 정렬을 자주하는 경우엔 배열을 사용하고, 추가/삭제가 많은 경우엔 연결리스트를 사용합니다.

 

선언

LinkedList<Integer> list = new LinkedList<>();

 

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

 

예제

LinkedList<Integer> 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<Integer> iterator = list.iterator(); //iterator 선언
while(iter.hasNext()){ //다음 값이 있는지 체크함
	System.out.println(iter.next());
}

list.contains(1); //리스트에 1이 있는지 검색
list.indexOf(1); //1이 있는 index 반환