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

双向链表的基本操作

程序员文章站 2024-03-22 11:17:16
...
class ListNode{
	ListNode pre;
	int val;
	ListNode next;
	ListNode(int val){
		this.val=val;
	}
	ListNode(ListNode pre,int val,ListNode next){
		this.pre=pre;
		this.val=val;	
		this.next=next;
	}
}

public class Test {
	static ListNode head;//头节点
	static ListNode tail;//尾节点
	static int size;//链表长度
	/*
	 * 增加元素(尾部插入)
	 * */
	public static void add(int val) {
		ListNode node=new ListNode(tail,val,null);
		if(head==null) {
			head=node;
		}else {
			tail.next=node;
		}
		tail=node;
		size++;
	}
	/*
	 * 删除元素
	 * */
	public static boolean remove(int index) {
		if(index<0||index>size-1)
			return false;
		ListNode tmp;
		if(index<(size>>1)) {//index在链表前半段
			 tmp=head;
			for(int i=0;i<index;i++) {
				tmp=tmp.next;			
			}			
		}else {//index在链表后半段
			 tmp=tail;
			for(int i=size-1;i>index;i--) {
				tmp=tmp.pre;
			}
		}
		ListNode preNode=tmp.pre;//前驱节点
		ListNode nextNode=tmp.next;//后继节点
		if(preNode==null) {//待删节点是头节点
			head=nextNode;
		}else {//待删节点有前驱节点
			preNode.next=nextNode;
			tmp.pre=null;
		}
		if(nextNode==null) {//待删节点是尾节点
			tail=preNode;
		}else {//待删节点有后继节点
			nextNode.pre=preNode;
			tmp.next=null;
		}
		size--;
		return true;
	}
	/*
	 * 查找某一个索引位置的元素
	 * */
	public static int get(int index) {
		if(index<0||index>size-1) 
			return -1;
		ListNode tmp;
		if(index<(size>>1)) {//index在链表前半段
			 tmp=head;
			for(int i=0;i<index;i++) {
				tmp=tmp.next;
			}
			return tmp.val;
		} else {//index在链表后半段
			 tmp=tail;
			for(int i=size-1;i>index;i--) {
				tmp=tmp.pre;
			}
			return tmp.val;
		}
	}
	/*
	 * 修改某个元素的值
	 * */
	public static void set(int index,int val) {
		if(index<0||index>size-1)
			return ;
		
		if(index<(size>>1)) {
			ListNode tmp=head;
			for(int i=0;i<index;i++) {
				tmp=tmp.next;
			}
			tmp.val=val;			
		}else {
			ListNode tmp=tail;
			for(int i=size-1;i>index;i--) {
				tmp=tmp.pre;
			}
			tmp.val=val;
		}
	}
	/*
	 * 某个位置插入一个节点
	 * */
	public static boolean add(int index,int val) {
		if(index<0||index>size-1)
			return false;
		ListNode node=new ListNode(val);
		ListNode tmp;
		if(index<(size>>1)) {
			tmp=head;
			for(int i=0;i<index;i++) {
				tmp=tmp.next;
			}
		}else {
			tmp=tail;
			for(int i=size-1;i>index;i--) {
				tmp=tmp.pre;
			}
		}
		node.next=tmp;
		tmp.pre.next=node;
		node.pre=tmp.pre;
		tmp.pre=node;
		return true;
	}
	/*
	 * 打印链表
	 * */
	public static void print() {
		if(head==null)
			return ;
		ListNode tmp=head;
		while(tmp!=null) {
			System.out.print(tmp.val+" ");
			tmp=tmp.next;
		}
	}
	public static void main(String[] args) {
		add(1);
		add(2);
		add(3);
		add(4);
		add(5);
		System.out.println("链表长度:"+size);
		System.out.println("打印链表");
		print();
		set(2,7);
		System.out.println();
		System.out.println("把index为2的元素设为7后打印链表");
		print();
		remove(1);
		System.out.println();
		System.out.println("删除index为1的元素后打印链表");
		print();	
		System.out.println();
		add(2,6);
		System.out.println("在index为2的位置插入值为6的节点后打印链表");
		print();
	}

}

输出:
链表长度:5
打印链表
1 2 3 4 5
把index为2的元素设为7后打印链表
1 2 7 4 5
删除index为1的元素后打印链表
1 7 4 5
在index为2的位置插入值为6的节点后打印链表
1 7 6 4 5