数据结构之链表(1)

一直用到测试的表：

View Code

 1 //表
 2 public class Link
 3 {
 4     public int data ;
 5     public Link next ;
 6     
 7     //---------------------------------
 8     public Link(int data)
 9     {
10         this.data = data ;
11     }
12     //---------------------------------
13     public void displayLink()
14     {
15         System.out.print("{"+data+"}") ;
16     }
17 }

1.普通链表，从头部插入和删除

View Code

 1 //链表
 2 //普通链表,从头部插入和删除
 3 public class LinkList
 4 {
 5     private Link first ; 
 6     //-----------------------------------
 7     public LinkList()
 8     {
 9         first = null ;
10     }
11     //-----------------------------------
12     public boolean isEmpty()//返回链表是否为空
13     {
14         return first==null ;
15     }
16     //-----------------------------------
17     public void insertFirst(int data)//从头部插入表
18     {
19         Link newLink = new Link(data) ;
20         newLink.next = first ;
21         first = newLink ;
22     }
23     //-----------------------------------
24     public Link deleteFirst()//删除头部的表
25     {
26         Link temp = first ;
27         first = first.next ;
28         return temp ;
29     }
30     //-----------------------------------
31     public void displayList()//显示链表
32     {
33         System.out.print("List (first-->last): ") ;
34         Link current = first ;
35         while(current!=null)
36         {
37             current.displayLink() ;
38             current = current.next ;
39         }  
40         System.out.println() ;
41     }
42 }

View Code

 1 //测试接口
 2 public class LinkListApp
 3 {
 4    public static void main(String[] args)
 5    {
 6        LinkList theList = new LinkList() ;
 7        
 8        theList.insertFirst(1) ;
 9        theList.insertFirst(2) ;
10        theList.insertFirst(3) ;
11        theList.insertFirst(4) ;
12        
13        theList.displayList() ;
14        
15        while(!theList.isEmpty())
16        {
17            Link aLink = theList.deleteFirst() ;
18            System.out.print("Delete ") ;
19            aLink.displayLink() ;
20            System.out.println() ;
21         }
22     }
23 }

2.普通链表，从尾部插入，从头部删除

View Code

 1 //链表
 2 //普通链表，从尾部插入和从头部删除 
 3 public class LinkList2
 4 {
 5    private Link first ;//链表头部
 6    private Link foot ;//链表尾部
 7    //-----------------------------
 8    public LinkList2()
 9    {
10        first = null ;
11        foot = null ;
12     }
13    //-----------------------------
14    public boolean isEmpty()//判断链表是否为空
15    {
16        return first==null ;
17     }
18    //-----------------------------
19    public void insertFoot(int data)//从尾部插入
20    {
21        Link newLink = new Link(data) ;
22        if(isEmpty())
23        {
24            first = newLink ;
25            foot = newLink ;
26         }
27        else
28        {
29            foot.next = newLink ;
30            foot = newLink ;
31         }
32     }
33        //-----------------------------
34        public Link deleteFirst()//从头部删除
35        {
36            Link temp = first ;
37            first = first.next ;
38            return temp ;
39         }
40        //----------------------------- 
41        public void displayList()//显示链表
42        {
43            System.out.print("List (first-->last): ") ;
44            Link current = first ;
45            while(current!=null)
46            {
47                current.displayLink() ;
48                current = current.next ;
49            }  
50            System.out.println() ;
51         }
52 }

View Code

 1 //测试接口
 2 public class LinkListApp2
 3 {
 4    public static void main(String[] args)
 5    {
 6        LinkList2 theList = new LinkList2() ;
 7        
 8        theList.insertFoot(1) ;
 9        theList.insertFoot(2) ;
10        theList.insertFoot(3) ;
11        theList.insertFoot(4) ;
12        
13        theList.displayList() ;
14        
15        while(!theList.isEmpty())
16        {
17            Link aLink = theList.deleteFirst() ;
18            System.out.print("Delete ") ;
19            aLink.displayLink() ;
20            System.out.println() ;
21         }
22     }
23 }

3.查找和删除指定链接点

View Code

 1 //查找和删除指定链接点
 2 public class LinkList3
 3 {
 4     private Link first ;
 5     
 6     //--------------------------------
 7     public LinkList3()
 8     {
 9         first = null ;
10     }
11     //--------------------------------
12     public boolean isEmpty()//判断是否为空
13     {
14         return first==null ;
15     }
16     //--------------------------------
17     public void insertFirst(int data)//在头插入表
18     {
19         Link newLink = new Link(data) ;
20         newLink.next = first ;
21         first = newLink ;
22     }
23     //--------------------------------
24     public Link find(int key)//查询
25     {
26         Link current = first ;
27         while(current.data!=key)
28         {
29             if(current.next==null)
30                return null ;
31             else 
32                current = current.next ;
33         }
34         return current ;
35     }
36     //-----------------------------
37        public Link deleteFirst()//从头部删除
38        {
39            Link temp = first ;
40            first = first.next ;
41            return temp ;
42         }
43     //--------------------------------
44     public Link delete(int key)//删除
45     {
46        Link current = first ;
47        Link previous = first ;
48        while(current.data!=key)
49        {
50            if(current.next==null)
51               return null ;
52            else
53            {
54               previous = current ;
55               current = current.next ;
56             }
57         }
58        if(current == first)
59               first = first.next ;
60            else 
61               previous.next = current.next ;
62            return current ;
63     }
64     //--------------------------------
65     public void displayList()//显示链表
66     {
67         System.out.print("List(first-->last) :") ;
68         Link current = first ;
69         while(current!=null)
70         {
71             current.displayLink() ;
72             current = current.next ;
73         }
74         System.out.println() ;
75     }
76 }

View Code

 1 //测试接口
 2 public class LinkList3App
 3 {
 4    public static void main(String[] args)
 5    {
 6        LinkList3 theList = new LinkList3() ;
 7        
 8        theList.insertFirst(1) ;
 9        theList.insertFirst(2) ;
10        theList.insertFirst(3) ;
11        theList.insertFirst(4) ;
12        
13        theList.displayList() ;
14        
15        Link f = theList.find(4) ;
16        System.out.print("Find : ") ;
17        f.displayLink();
18        System.out.println() ;
19        
20        Link d = theList.delete(3) ;
21        System.out.print("Delete : ") ;
22        d.displayLink() ;
23        System.out.println() ;
24        
25        theList.displayList() ;
26        
27        while(!theList.isEmpty())
28        {
29            Link aLink = theList.deleteFirst() ;
30            System.out.print("Delete ") ;
31            aLink.displayLink() ;
32            System.out.println() ;
33         }
34     }
35 }

4.双端链表，即链表同时记录头和尾，可以在头部和尾部插入，但只能在头部删除

View Code

 1 //双端链表
 2 public class FirstLastList
 3 {
 4     private Link first ;
 5     private Link last ;
 6     //--------------------------------
 7     public FirstLastList()
 8     {
 9         first = null ;
10         last = null ;
11     }
12     //--------------------------------
13     public boolean isEmpty()//判断是否为空
14     {
15         return first==null ;
16     }
17     //--------------------------------
18     public void insertFirst(int data)//从链表头插入
19     {
20         Link newLink = new Link(data) ;
21         if(isEmpty())
22            last = newLink ;
23         newLink.next = first ;
24         first = newLink ;
25     }
26     //--------------------------------
27     public void insertLast(int data)//从链表尾插入
28     {
29         Link newLink = new Link(data) ;
30         if(isEmpty())
31            first = newLink ;
32         else
33            last.next = newLink ;
34         last = newLink ;
35     }
36     //--------------------------------
37     public Link deleteFirst()//从头部删除
38     {
39         Link temp = first ;
40         if(first.next==null)
41            last=null;
42         first = first.next ;
43         return temp ;
44     }
45     //--------------------------------
46     public void displayList()//显示链表
47     {
48         System.out.print("List(first-->last) :") ;
49         Link current = first ;
50         while(current!=null)
51         {
52             current.displayLink() ;
53             current = current.next ;
54         }
55         System.out.println() ;
56     }
57 }

View Code

 1 //双端链表测试接口
 2 public class FirstLastListApp
 3 {
 4    public static void main(String[] args)
 5    {
 6       FirstLastList theList = new FirstLastList() ;
 7       theList.insertFirst(3) ;//从头部插入
 8       theList.insertFirst(2) ;
 9       theList.insertFirst(1) ;
10       
11       theList.displayList() ;
12       
13       theList.insertLast(4) ;//从尾部插入
14       theList.insertLast(5) ;
15       theList.insertLast(6) ;
16       
17       theList.displayList() ;
18       
19       for(int i=0 ;i<3 ; i++)//从头部删除
20       {
21            Link d = theList.deleteFirst() ;
22            System.out.print("Delete : ") ;
23            System.out.println(d.data) ;
24       } 
25       
26       theList.displayList() ;
27    }
28 }

5.通过链表实现栈的功能。栈是先进后出（FILO），则该使用普通链表，即在头部插入和删除

View Code

 1 //链表
 2 //普通链表,从头部插入和删除（通过链表实现栈）
 3 public class LinkList4
 4 {
 5     private Link first ; 
 6     //-----------------------------------
 7     public LinkList4()
 8     {
 9         first = null ;
10     }
11     //-----------------------------------
12     public boolean isEmpty()//返回链表是否为空
13     {
14         return first==null ;
15     }
16     //-----------------------------------
17     public void insertFirst(int data)//从头部插入表
18     {
19         Link newLink = new Link(data) ;
20         newLink.next = first ;
21         first = newLink ;
22     }
23     //-----------------------------------
24     public int deleteFirst()//删除头部的表
25     {
26         Link temp = first ;
27         first = first.next ;
28         return temp.data ;
29     }
30     //-----------------------------------
31     public void displayList()//显示链表
32     {
33         System.out.print("List (first-->last): ") ;
34         Link current = first ;
35         while(current!=null)
36         {
37             current.displayLink() ;
38             current = current.next ;
39         }  
40         System.out.println() ;
41     }
42 }

View Code

 1 //栈类
 2 public class LinkStack
 3 {
 4     private LinkList4 theList ;
 5     //---------------------------------
 6     public LinkStack()
 7     {
 8         theList = new LinkList4() ;
 9     }
10     //---------------------------------
11     public void push(int data)//入栈
12     {
13         theList.insertFirst(data) ;
14     }
15     //---------------------------------
16     public int pop()//出栈
17     {
18         return theList.deleteFirst() ;
19     }
20     //---------------------------------
21     public boolean isEmpty()//判断是否为空
22     {
23         return theList.isEmpty() ;
24     }
25     //---------------------------------
26     public void displayStack()//显示栈
27     {
28         theList.displayList() ;
29     }
30 }

View Code

 1 //栈测试接口
 2 public class LinkStackApp
 3 {
 4    public static void main(String[] args)
 5    {
 6        LinkStack theStack = new LinkStack() ;
 7        theStack.push(20) ;
 8        theStack.push(30) ;
 9        theStack.push(40) ;
10        
11        theStack.displayStack() ;
12        
13        System.out.print("pop() :"+theStack.pop()+" "+theStack.pop()) ;
14        System.out.println() ;
15        
16        theStack.displayStack() ;
17     }
18 }

6.通过链表实现队列的功能。队列是先进先出(FIFO)，则应该考虑使用双端链表，可以尾部插入，但只能在头部删除

View Code

 1 //双端链表,通过双端链表实现队列
 2 public class FirstLastList2
 3 {
 4     private Link first ;
 5     private Link last ;
 6     //--------------------------------
 7     public FirstLastList2()
 8     {
 9         first = null ;
10         last = null ;
11     }
12     //--------------------------------
13     public boolean isEmpty()//判断是否为空
14     {
15         return first==null ;
16     }
17     //--------------------------------
18     public void insertFirst(int data)//从链表头插入
19     {
20         Link newLink = new Link(data) ;
21         if(isEmpty())
22            last = newLink ;
23         newLink.next = first ;
24         first = newLink ;
25     }
26     //--------------------------------
27     public void insertLast(int data)//从链表尾插入
28     {
29         Link newLink = new Link(data) ;
30         if(isEmpty())
31            first = newLink ;
32         else
33            last.next = newLink ;
34         last = newLink ;
35     }
36     //--------------------------------
37     public int deleteFirst()//从头部删除
38     {
39         Link temp = first ;
40         if(first.next==null)
41            last=null;
42         first = first.next ;
43         return temp.data ;
44     }
45     //--------------------------------
46     public void displayList()//显示链表
47     {
48         System.out.print("List(first-->last) :") ;
49         Link current = first ;
50         while(current!=null)
51         {
52             current.displayLink() ;
53             current = current.next ;
54         }
55         System.out.println() ;
56     }
57 }

View Code

 1 //队列
 2 public class LinkQueue
 3 {
 4    private FirstLastList2 theList ;
 5    //------------------------------------
 6    public LinkQueue()
 7    {
 8        theList = new FirstLastList2() ;
 9     }
10    //------------------------------------
11    public boolean isEmpty()//判断是否为空
12    {
13        return theList.isEmpty() ;
14     }
15    //------------------------------------
16    public void insert(int data)//入列
17    {
18       theList.insertLast(data) ;  
19     }
20    //------------------------------------
21    public int remove()//出列
22    {
23       return theList.deleteFirst() ;
24     }
25    //------------------------------------
26    public void displayQueue()//显示队列
27    {
28        theList.displayList() ;
29     }
30 }

View Code

 1 //列表测试接口
 2 public class LinkQueueApp
 3 {
 4     public static void main(String[] args)
 5     {
 6         LinkQueue theQueue = new LinkQueue() ;
 7         theQueue.insert(20) ;
 8         theQueue.insert(30) ;
 9         theQueue.insert(40) ;
10         theQueue.insert(50) ;
11         
12         theQueue.displayQueue() ;
13         
14         System.out.print("remove() :"+theQueue.remove()+" "+theQueue.remove()) ;
15         System.out.println() ;
16         
17         theQueue.displayQueue() ; 
18     }
19 }

keeping on......