LinkedList 구조

 

 

 

■ LinkedList

Linked List는 각 노드(객체)의 데이터와 포인터를 가지고 있는데 데이터를 담고 있는 노드들이 연결되어있고, 노드의 포인터가 이전 노드의 주소와 다음 노드의 주소를 참조함으로서 구성된다.  ArrayList에 비해서 데이터의 추가 삭제는 용이하나 탐색이 필요한 경우에는 속도가 떨어지는 단점이 있다. 

 

 

 

 

 

 

 

 

● LinkedList의 종류

종류에 따라 next만 쓰는 경우 prev와 함께 쓰는 경우 등 다르게 사용된다.

public class Node {

	Node next; // 다음 노드 주소를 저장하는 필드
	Node prev; // 이전 노드 주소를 저장하는 필드
	int data; // 데이터를 저장하는 필드
}

 

 

 

 

 

 

• singly linked list

다음 노드를 가리키기 위한 포인터 필드만을 가지고 있는 리스트이다. 현재 요소에서 이전 요소로 이동하기 위해서는 n번 이동을 해야한다는 단점이 있다.

 

 

 

• doubly linked list

기존의 단일 연결 리스트에서 이전 노드의 주소를 담고 있는 필드가 추가된 형태로, 역순으로도 검색이 가능하여 단일연결 리스트보다 각 요소에 대한 접근과 이동이 쉽다.

 

 

 

• doubly circular linked list

doubly linked list에서 첫번째 노드와 마지막 노드를 각각 연결시켜, 마치 원형 리스트처럼 만든것이다.

 

 

 

 

 

 

 

● LinkedList 사용법

LinkedList는 List 자료구조 외에도 Stack이나 Queue 자료구조도 이용이 가능하다

 

 

 

 

 

• LinkedList 객체 생성

배열처럼 미리 공간을 할당하고 사용하는 방식이 아니라 데이터가 추가될때마다 노드가 생성되어 동적으로 추가되는 방식이다.

	LinkedList<Integer> list = new LinkedList<>();
	
	// 생성시 초기값 설정
	LinkedList<Integer> list2 = new LinkedList<>(Arrays.asList(38,28,18));

 

 

 

 

 

 

• LinkedList 요소 추가

ArrayList와 다르게 데이터가 추가되거나 데이터가 삭제되어도 앞으로 당겨지거나 뒤로 밀리는 동작이 없다. 즉 추가되거나 삭제될 노드 위치의 바로 앞뒤쪽에 있는 노드의 참조를 변경하기만 하면된다.

		LinkedList<Integer> list2 = new LinkedList<>(Arrays.asList(38,28,18));
		
		// 가장 앞에 데이터 추가
		list2.addFirst(48);
		
		// index 2에 30이라는 데이터 추가
		list2.add(2,30);
		
		// 가장 마지막에 데이터 추가
		list2.addLast(66);
		
		System.out.println(list2); // 48,38,30,28,18,66

 

 

 

 

 

 

 

• LinkedList 요소 삭제

add() 메소드 처럼 removeFirst(), removeLast() 등 이 있으며 값을 전부 제거 하고싶다면 clear() 메소드를 사용할 수 있다.

		LinkedList<Integer> list2 = new LinkedList<>(Arrays.asList(38,28,18,50,12));
		
		// 가장 마지막 데이터 삭제
		list2.removeLast();
		
		// 해당 index 위치의 데이터 삭제
		list2.remove(2);
		
		// 모든 값 제거
		list2.clear();
		
		System.out.println(list2);

 

 

 

 

 

 

 

• LinkedList 요소 검색

인덱스 위치를 반환해주는 indexOf() 메소드와 요소가 List에 포함되어 있는지 확인해주는 contains()메소드 등이 있다.

		LinkedList<String> list = new LinkedList<>(Arrays.asList("손흥민","김민재","황희찬","정우영"));
		
		
		// LinkedList에 저장된 객체의 개수를 반환
		System.out.println(list.size());
		
		// 지정된 객체가 list에 포함되어 있는지 확인한다.(boolean 타입)
		System.out.println(list.contains("손흥민"));
		
		
		// 해당 값을 가지고 있는 요소 위치를 반환한다
		System.out.println(list.indexOf("정우영"));
		
		// 해당 값을 가지고 있는 요소 위치 반환 (뒤에서 부터 검색하며 값이 없으면 -1)
		System.out.println(list.lastIndexOf("이강인"));

 

 

 

 

 

 

 

•  LinkedList 값 출력

get() 메소드는 해당 index에 해당하는 데이터를 출력한다.

		LinkedList<String> list = new LinkedList<>(Arrays.asList("손흥민","김민재","황희찬"));
		
		list.add("이강인");
		list.add("김병지");
		
		
		// 향상 for문으로 출력
		for(String result : list) {
			System.out.println(result);
		}

		// get() 메소드를 활용하여 출력
		for(int i = 0; i < list.size(); i++) {
			System.out.println(list.get(i));
		}
		
		// Iterator 사용하여 출력 
		Iterator iter = list.iterator();
		
		while(iter.hasNext()) {
			System.out.println(iter.next());

 

 

 

 

 

 

 

 

 

---

 

 

 

 

Today short review 

LinkedList에 대해 알아보았는데 ArrayList와 비교하며 알아보는것도 좋은 방법일거 같다