[자료구조] 연결 리스트(Linked List)

연결 리스트(Linked List)

• 연속적인 메모리 위치에 저장되지 않는 선형 데이터 구조
• 각 노드는 데이터 필드와 다음 노드에 대한 참조를 포함하는 노드로 구성
  
  

연결 리스트(Linked List) 사용 이유

• 배열은 비슷한 유형의 선형 데이터를 저장하는데 사용할 수 있지만 제한 사항이 있음
  1. 배열의 크기가 고정되어 있어 미리 요소의 수에 대해 할당을 받아야 함
  2. 새로운 요소를 삽입하는 것은 비용이 많이 듬
  
  

장점

1. 동적 크기
2. 삽입/삭제 용이

단점

1. 임의로 액세스를 허용할 수 없음
   → 즉, 첫 번째 노드부터 순차적으로 요소에 액세스 해야함
2. 포인터의 여분이 메모리 공간이 목록의 각 요소에 필요
   
   

LinkedList 선언

LinkedList list = new LinkedList();//타입 미설정 Object로 선언된다.
LinkedList<Student> members = new LinkedList<Student>();//타입설정 Student객체만 사용가능
LinkedList<Integer> num = new LinkedList<Integer>();//타입설정 int타입만 사용가능
LinkedList<Integer> num2 = new LinkedList<>();//new에서 타입 파라미터 생략가능
LinkedList<Integer> list2 = new LinkedList<Integer>(Arrays.asList(1,2));//생성시 값추가

 

LinkedList 값 추가

LinkedList<Integer> list = new LinkedList<Integer>();
list.addFirst(1);//가장 앞에 데이터 추가
list.addLast(2);//가장 뒤에 데이터 추가
list.add(3);//데이터 추가
list.add(1, 10);//index 1에 데이터 10 추가

LinkedList<Student> list = new LinkedList<Student>();
Student student = new Student(name,age);
members.add(student);
members.add(new Member("홍길동",15));

 

LinkedList 값 삭제

LinkedList<Integer> list = new LinkedList<Integer>(Arrays.asList(1,2,3,4,5));
list.removeFirst(); //가장 앞의 데이터 제거
list.removeLast(); //가장 뒤의 데이터 제거
list.remove(); //생략시 0번째 index제거
list.remove(1); //index 1 제거
list.clear(); //모든 값 제거

 

LinkedList 값 출력

LinkedList<Integer> list = new LinkedList<Integer>(Arrays.asList(1,2,3));

System.out.println(list.get(0));//0번째 index 출력
				
for(Integer i : list) { //for문을 통한 전체출력
    System.out.println(i);
}

Iterator<Integer> iter = list.iterator(); //Iterator 선언 
while(iter.hasNext()){//다음값이 있는지 체크
    System.out.println(iter.next()); //값 출력
}

 

LinkedList 값 검색

LinkedList<Integer> list = new LinkedList<Integer>(Arrays.asList(1,2,3));
System.out.println(list.contains(1)); //list에 1이 있는지 검색 : true
System.out.println(list.indexOf(1)); //1이 있는 index반환 없으면 -1