算法:双链表的实现

冬至到了，这几天在复习，对于数据结构，只是重新温故了一下链表的知识，在老朱的帮助下，算是对链表有个大致的了解

双链表的实现

//双链表操作
//需要借助两个标记结点，一个作为头结点，一个作为尾结点
import java.util.ArrayList;
import java.util.LinkedList;
public class MyLinklist
{
	private static Node beginMaker=new Node(-1,null,null);//头节点
	private static Node endMaker=new Node(-1,beginMaker,null);//尾节点
	static
	{
		beginMaker.next=endMaker;
	}
	private static class Node
	{
		//嵌套的Node类
		public Node(int d,Node p,Node  n)
		{
			data=d;//数据域
			prev=p;//前趋指针
			next=n;//后继指针
		}
		
		public Node(int d)
		{
			data=d;
		}

		public int 	 data;//数据域
		public Node  prev;//前趋指针
		public Node  next;//后继

	}
	//清除结点
	private void doClear()
	{
		beginMaker= new Node(-1,null,null);
		endMaker= new Node(-1, beginMaker,null);//Node.prev=beginMaker整个链表只剩下beginMaker和endMaker
		beginMaker.next=endMaker;
	}
	
	//正序输出
	private void display()
	{
		System.out.println("正序输出！");
		Node p=beginMaker;
		while(p!=null)
		{
			System.out.println(p.data);
			p=p.next;
		}
	}
	//逆序输出!
	private void reversedisplay()
	{
		System.out.println("逆序输出！");
		Node p=endMaker;
		while(p!=null)
		{
			System.out.println(p.data);
			p=p.prev;
		}
	}
	
	//在尾部追加结点
	private void addBefore(Node p,int x)
	{
		Node newNode=new Node(x,p.prev,p);
		newNode.prev.next=newNode;
		p.prev=newNode;
	}


	//在某个结点前增加结点
	private void add(int key,int x)
	{
		System.out.println("开始在结点前追加!");
		Node node=new Node(key);
		Node p=beginMaker;
		while(p.next!=null)
		{
			if(p.next.data==x)
			{
				node.next=p.next;
				node.prev=p;
				p.next.prev=node;
				p.next=node;
				return;
			}
			p=p.next;
		}
		System.out.println("找不到这个节点，不能增加");
	}
	//删除结点
	private void delete(int key)
	{
		System.out.println("开始删除!");
		Node p=beginMaker;//头指针
		while(p.next!=null)
		{
			if(p.data==key)
			{
				p.prev.next=p.next;
				p.next.prev=p.prev;
				System.out.println("删除成功!删除了"+key);
				System.out.println(p.data);
				p.next=null;
				p.prev=null;
				System.gc();
				return;
			}
			p=p.next;//这行代码我总是错，这个p引用就相当于beginMaker，都指向了同一个结点的地址			
			
		}
		System.out.println("找不到此节点,删除失败!");
	}
	
	
	public static void main(String[] args) {
			MyLinklist l=new MyLinklist();
			//在此处创建结点
			for(int i=0;i<10;i++)
				l.addBefore(endMaker, i);
			l.delete(5);//删除值为5的结点
			l.display();
			l.add(5,6);//在值为6的结点前追加结点
			l.display();
		}
}

今天每位考研的学长学姐，你们都是最棒的～!364天了，加油!