[데이터 구조] 싱글 체인 시트, 더 블 엔 드 링크, 질서 있 는 링크
17754 단어 데이터 구조
단 방향 링크
더 블 엔 드 링크
질서 있 는 링크
LeetCode 를 칠 할 때 링크 의 제목 인 Merge Two Sorted Lists 를 만 났 는데 자신 이 답 을 알 아 보지 못 한 다 는 것 을 알 게 되 었 다 (데이터 구 조 를 체계적으로 학습 하지 않 았 기 때문에 T T).
그래서 데이터 구조의 학습 을 열심히 실천 하기 로 마음 먹었다.링크 는 배열 에 비해 데이터 삽입 과 삭제 효율 이 높다.어떤 노드 에 무 작위 로 접근 하 는 데 이 터 는 배열 보다 빠 릅 니 다.
다음은 자바 가 실현 한 각종 링크 입 니 다.
단 방향 링크
링크 의 조작 을 바느질 에 비유 하면 선 은 모든 노드 간 의 next 침 은 복 제 된 모든 지향 노드 의 Data 이다.
넥 스 트 가 '=' 의 왼쪽 에 나타 나 야만 링크 의 구조 가 실질 적 으로 바 뀔 수 있다.
insertFirst: 표 머리 에 새로운 노드 를 삽입 합 니 다. 시간 복잡 도 는 O (1) deleteFirst 입 니 다. 표 머리의 노드 를 삭제 하고 시간 복잡 도 는 O (1) 입 니 다. 이 두 가지 방법 이 있 으 면 하나의 스 택 을 단일 체인 표 로 실현 할 수 있 습 니 다. find: 지정 한 키 워드 를 포함 하 는 노드 를 찾 습 니 다. 두루 찾 아야 하기 때문에 평균 N/2 번, 즉 O (N) 를 찾 아야 합 니 다.remove: 지정 한 키 워드 를 포함 하 는 노드 를 삭제 합 니 다. 검색 을 옮 겨 다 녀 야 하기 때문에 평균 N/2 번, 즉 O (N) 를 찾 아야 합 니 다.
public class LinkedList {
public static void main(String[] args) {
}
class Data{
Object obj;
Data next = null;
Data(Object obj){
this.obj = obj;
}
}
Data first = null;
//
public void insertFirst(Object obj){
Data data = new Data(obj);
data.next = first;
first = data;
}
//
public Object deleteFirst()throws Exception{
if(first==null)
throw new Exception("empty");
Data temp = first;
first = first.next;
return temp.obj;
}
//
public Object find(Object obj)throws Exception{
if(first==null)
throw new Exception("empty");
Data cur = first;
while(cur!=null){
if(cur.obj.equals(obj))
return cur.obj;
cur = cur.next;
}
return null;
}
//
public boolean isEmpty(){
return first==null;
}
//
public void remove(Object obj)throws Exception{
if(first==null)
throw new Exception("empty");
if(first.obj.equals(obj)){ //
first = first.next;
}else{
Data pre = first;
Data cur = first.next;
while(cur!=null){
if(cur.obj.equals(obj)){
pre.next = cur.next;
break;
}
pre = cur;
cur = cur.next;
}
}
}
//
public void removeAll(Object obj)throws Exception{
if(first==null)
throw new Exception("empty");
while(first.obj.equals(obj)){
first = first.next;
}
Data pre = first;
Data cur = first.next;
while(cur!=null){
if(cur.obj.equals(obj)){
pre.next = cur.next;
pre = pre.next;
cur = pre.next; // pre.next
continue; // ，
}
pre = cur;
cur = cur.next;
}
}
//
public void display()throws Exception{
if(first == null)
throw new Exception("your list is empty");
Data cur = first;
while(cur!=null){
System.out.print(cur.obj.toString()+"->");
cur = cur.next;
}
System.out.println();
}
}
1 -> 2 -> 3 -> 4 ->
2 -> 3 -> 4 ->
2 -> 4 ->
null
4 양 끝 링크
양 끝 링크 는 양 방향 링크 가 아니 라 양 끝 은 마지막 노드 의 참조 (last) 에 불과 합 니 다.
insert First: 표 머리 에 새로운 노드 를 삽입 합 니 다. 시간 복잡 도 O (1) insert Last: 표 끝 에 새로운 노드 를 삽입 합 니 다. 시간 복잡 도 O (1) deleteFirst: 표 머리의 노드 를 삭제 합 니 다. 시간 복잡 도 O (1) deleteLast: 표 끝의 노드 를 삭제 합 니 다. 표 끝의 노드 만 저장 되 어 있 기 때문에 표 끝의 앞 노드 (단 방향, 뒤로 만 밀 수 있 습 니 다) 를 저장 하지 않 습 니 다.따라서 표 끝 노드 를 삭제 할 때 표 끝 노드 의 앞 노드 를 찾 으 려 면 N - 1 번, 즉 O (N) 를 찾 아야 합 니 다.
2 단 링크 로 대기 열 을 실현 하 다.
public class FirstLastList {
private class Data{
private Object obj;
private Data next = null;
Data(Object x){
this.obj = x;
}
}
Data first = null;
Data last = null;
public void insertFirst(Object obj){
Data data = new Data(obj);
if(first==null)
last=data;
data.next = first;
first = data;
}
public void insertLast(Object obj){
Data data = new Data(obj);
if(first==null){
first = data;
}else{
last.next = data;
}
last = data;
}
public Object deleteFirst()throws Exception{
if(first==null)
throw new Exception("empty!");
Data temp = first;
if(first.next==null)
last = null;
first = first.next; //if first.next = null that means first = null
return temp.obj;
}
public void deleteLast()throws Exception{
if(first==null)
throw new Exception("empty!");
if(first.next==null){ //single node scenario
first = null;
last = null;
}else{
Data cur = first;
while(cur.next!=null){ //stop by end
if(cur.next==last){
last = cur;
last.next = null;
break; // break ？？ cur = cur.next
}
cur = cur.next;
}
}
}
public void display()throws Exception{
if(first == null)
throw new Exception("your list is empty");
Data cur = first;
while(cur!=null){
System.out.print(cur.obj.toString()+"->");
cur = cur.next;
}
System.out.println();
}
public static void main(String[] args) throws Exception {
FirstLastList fll = new FirstLastList();
fll.insertFirst(2);
fll.insertFirst(1);
fll.display();
fll.insertLast(3);
fll.display();
fll.deleteFirst();
fll.display();
fll.deleteLast();
fll.display();
}
}
1 -> 2 ->
1 -> 2 -> 3 ->
2 -> 3 ->
2 -> 질서 있 는 링크
단 방향 링크 는 삽입 할 때 순 서 를 정할 뿐이다.
표 의 삽입 과 삭 제 는 평균 N/2 회, 즉 O (N) 를 비교 해 야 하지만 최소 데이터 항목 을 얻 으 려 면 O (1) 만 필요 합 니 다. 항상 표 머리 에 있 기 때문에 최소 데이터 항목 을 자주 조작 하 는 응용 은 질서 있 는 링크 를 사용 하여 이 루어 지 는 것 을 고려 할 수 있 습 니 다. 예 를 들 어 우선 순위 대기 열 등 입 니 다.
public class SortedList {
private class Data{
private Object obj;
private Data next = null;
Data(Object obj){
this.obj = obj;
}
}
private Data first = null;
public void insert(Object obj){
Data data = new Data(obj);
Data pre = null;
Data cur = first;
while(cur!=null&&Integer.valueOf(data.obj.toString()).intValue()>
Integer.valueOf(cur.obj.toString()).intValue()){
pre = cur;
cur = cur.next;
}
if(pre==null)
first = data;
else
pre.next = data;
data.next = cur;
}
public Object deleteFirst()throws Exception{
if(first==null)
throw new Exception("empty");
Data temp = first;
first = first.next;
return temp.obj;
}
public void display(){
if(first == null)
System.out.println("empty");
System.out.print("first -> last : ");
Data cur = first;
while(cur != null){
System.out.print(cur.obj.toString() + " -> ");
cur = cur.next;
}
System.out.print("
");
}
public static void main(String[] args) throws Exception{
SortedList sl = new SortedList();
sl.insert(80);
sl.insert(2);
sl.insert(100);
sl.display();
System.out.println(sl.deleteFirst());
sl.insert(33);
sl.display();
sl.insert(99);
sl.display();
}
}
first -> last : 2 -> 80 -> 100 ->
2
first -> last : 33 -> 80 -> 100 ->
first -> last : 33 -> 80 -> 99 -> 100 -> 좋은 웹페이지 즐겨찾기
