欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构与算法 双链表

程序员文章站 2024-03-16 15:26:22
...
package linkedlist;



public class DoubleLinkedListDemo {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		DoubleLinkedList dl=new DoubleLinkedList();
		System.out.println(dl.getLength());
		dl.add(1, 1);
		System.out.println(dl.getLength());
		dl.show();
		dl.add(2, 2);
		dl.add(3, 3);
		dl.add(4, 4);
		dl.show();
		dl.del(3);
		dl.show();
	}

}


class DoubleLinkedListNode{
	public int val;
	public DoubleLinkedListNode pre;
	public DoubleLinkedListNode next;
	public DoubleLinkedListNode(int val) {
		this.val=val;
	}
	public DoubleLinkedListNode() {
		// TODO Auto-generated constructor stub
	}
}

class DoubleLinkedList{
	public DoubleLinkedListNode head;

	public DoubleLinkedList(int val) {
		head=new DoubleLinkedListNode();
		head.val=val;
		head.next=null;
		head.pre=null;
	}
	
	public DoubleLinkedList() {
		// TODO Auto-generated constructor stub
		head=new DoubleLinkedListNode();
	}

	//获取双向链表的长度
	public int getLength() {
		DoubleLinkedListNode p=head.next;
		int length=0;
		while(p!=null) {
			length++;
			p=p.next;
		}
		return length;
	}
	
	//显示双向链表
	public void show() {
		DoubleLinkedListNode p=head.next;
		System.out.print("list:");
		while(p!=null) {
			System.out.printf("%d\t",p.val);
			p=p.next;
		}
		System.out.println();
	}
	
	//在指定位置插入
	public void add(int position,int val) {
		if(position<0||position>getLength()+1) {
			System.out.println("invalid position");
		}else {
			DoubleLinkedListNode p=head;
			for(int i=0;i<position-1;i++) {
				p=p.next;
			}
			DoubleLinkedListNode d=new DoubleLinkedListNode(val);
			if(p.next==null) {
				p.next=d;
				d.pre=p;
			}else {
				p.next.pre=d;
				d.pre=p;
				d.next=p.next;
				p.next=d;
				System.out.println("ok");
			}
			
		}
	}
	
	//删除指定位置的节点
	public void del(int position) {
		
		if(position<=0||position>getLength()) {
			System.out.println("invalid position");
		}else {
			DoubleLinkedListNode p=head;
			for(int i=0;i<position-1;i++) {
				p=p.next;
			}
			p.next.next.pre=p;
			p.next=p.next.next;
			System.out.println("del position:"+position);
		}
	}
	
}