首页 > 编程语言 > 详细

关于JAVA数据结构_线性表(通过双向链表实现)的学习

时间:2020-09-29 23:27:27      阅读:2      评论:0      收藏:0      [点我收藏+]

标签:最后一个元素   contain   相同   @override   args   插入元素   

list接口:

 1 package demo1;
 2 
 3 public interface MyList {
 4 
 5     int getSize();//返回线性表中元素的个数
 6     boolean isEmpty();//判断线性表是否为空
 7     void insert(int i,Object e);//在线性表的i索引值添加元素e
 8     boolean contains(Object e);//判断线性表中元素e的索引值
 9     int indexOf(Object e);//返回线性表中元素e的索引值
10     Object remove(Object e);//删除线性表第一个与e相同的元素,并返回该元素
11     Object remove(int i);//删除线性表第一个与i相同的元素,并返回该元素
12     Object replace(int i,Object e);//使用元素e代替i,并返回就得元素
13     Object get(int i);//返回索引值为i的元素
14     boolean insertBefore(Object p,Object e);//在线性表元素p前面插入元素e
15     boolean insertAfter(Object p,Object e);//在线性表元素p后面插入元素e
16     
17 
18 }

通过双向链表实现:

  1 package demo1;
  2 /**
  3  * 双向列表
  4  * @author ASUS
  5  *
  6  */
  7 public class MyDualLinkedList implements MyList {
  8     private Node first;  //指向前结点
  9     private Node last;  //指向尾结点
 10     private int size;   //保存元素的个数
 11     
 12     //返回元素的个数
 13     @Override
 14     public int getSize() {
 15 
 16         return size;
 17     }
 18 
 19     //判断链表是否为空
 20     @Override
 21     public boolean isEmpty() {
 22 
 23         return size==0;
 24     }
 25 
 26     //在指定位置插入元素
 27     @Override
 28     public void insert(int i, Object e) {
 29         //1.检查索引是否越界
 30         checkIndex(i);        
 31         //2.如果i==0;
 32         if(i==0){
 33             addFirst(e);
 34         }else if(i==size){
 35         //3.如果i==size,在尾部添加
 36             addLast(e);
 37         }else{
 38         //4.列表中心添加
 39             //找到i结点,在i结点前面插入元素
 40             Node pNode=getNode(i);
 41             Node PrevNode=pNode.prev;
 42             //生成新的结点
 43             Node newNode=new Node(e, PrevNode, pNode);
 44             //修改前驱结点的后缀
 45             
 46             PrevNode.next=newNode;
 47             pNode.prev=newNode;
 48             size++;
 49             
 50             
 51         }
 52     }
 53 
 54     //返回索引值对应的结点
 55     private Node getNode(int i) {
 56         //
 57         Node pNode=first;
 58         for(int x=0;x<i;x++){
 59             pNode=pNode.next;
 60         }
 61         return pNode;
 62     }
 63 
 64     
 65     //判断链表中是否包含指定的元素e,如果存在返回true
 66     @Override
 67     public boolean contains(Object e) {
 68 
 69         return indexOf(e)>=0;
 70     }
 71 
 72     //判断元素e在链表中第一次出现的位置,如果不存在返回-1
 73     @Override
 74     public int indexOf(Object e) {
 75         int i=0;
 76         //依次遍历链表中各个结点,比较结点的元素与指定的e是否一样
 77         if(e==null){
 78             for(Node pNode=first;pNode!=null;pNode=pNode.next){
 79                 if(pNode.data==null){
 80                     return i;
 81                 }
 82                 i++;
 83             }
 84         }else{
 85             for(Node pNode=first;pNode!=null;pNode=pNode.next){
 86                 if(e.equals(pNode.data)){
 87                     return i;
 88                 }
 89                 i++;
 90             }
 91             
 92         }
 93         return -1;
 94     }
 95     
 96     //从链表中删除指定元素,并返回删除元素
 97     @Override
 98     public Object remove(Object e) {
 99         //找到元素e对应的元素
100         int index=indexOf(e);
101         if(index<0){
102             return null;
103         }
104         return remove(index);
105     }
106 
107     //从链表中删除指定索引的元素,并返回删除的元素
108     @Override
109     public Object remove(int i) {
110         //判断索引值是否越界
111         checkIndex(i);
112         //找到对应的结点
113         Node pNode=getNode(i);
114         Node prevNode=pNode.prev;
115         Node nextNode=pNode.next;
116         if(prevNode==null){
117             //删除头结点
118             first=nextNode;
119         }else{
120             prevNode.next=nextNode;
121         }
122         if(nextNode==null){
123             //删除尾结点
124             last=prevNode;
125         }else{
126             nextNode.prev=prevNode;
127             
128         }
129         size--;
130         return pNode.data;
131     }
132 
133     //修改指定索引值得元素
134     @Override
135     public Object replace(int i, Object e) {
136         //检查是否越界
137         checkIndex(i);
138         //找到索引值为i的结点
139         Node pNode=getNode(i);
140         Object old =pNode.data;
141         pNode.data=e;
142         
143         
144         return old;
145     }
146 
147     //返回线性表中i索引值的元素
148     @Override
149     public Object get(int i) {
150         //判断是否越界
151         checkIndex(i);
152         Node pNode=getNode(i);
153          return pNode.data;
154     }
155 
156     
157     //在指定元素p前面插入元素e
158     @Override
159     public boolean insertBefore(Object p, Object e) {
160         //找到p元素在链表中的位置
161         int index =indexOf(p);
162         if(index<0){
163             return false;
164         }
165         insert(index,e);
166         return true;
167     }
168     //在指定元素p后面插入元素e
169     @Override
170     public boolean insertAfter(Object p, Object e) {
171         int index=indexOf(p);
172         if(index<0){
173             return false;
174         }
175         insert(index+1,e);
176         return true;
177     }
178     //检查索引值是否越界
179         private void checkIndex(int i){
180             if(i<0||i>size){
181                 throw new IndexOutOfBoundsException(i+"越界");
182             }
183         }
184         
185         @Override
186         public String toString() {
187             //依次遍历各个结点,吧元素转化为字符串
188             StringBuilder sb=new StringBuilder();
189             sb.append("[");
190             for(Node node=first;node!=null;node=node.next){
191                 sb.append(node.data);
192                 if(node!=last){
193                     sb.append(",");
194                     
195                 }
196             }
197             sb.append("]");
198             return sb.toString();
199         }
200        //常用对头结点和尾结点的操作
201         //在头部添加元素
202         public void addFirst(Object e){
203             Node pNode = first;
204             //生成一个新的结点
205             Node newNode=new Node(e,null,first);
206                 first = newNode;   //修改first指向新的结点
207                 if(pNode==null){
208                     last=newNode;
209                 }else{
210                     pNode.prev=newNode;
211                 }
212                 size++;  //元素个数加一
213             }
214         //在尾部添加
215         public void addLast(Object e){
216             Node pNode=last;
217             //生成一个新的结点
218             Node newNode=new Node(e,last,null);
219             if(pNode==null){
220                 first=newNode;
221             }else{
222                 pNode.next=newNode;
223             }
224             last=newNode;
225             size++;            
226         }
227         //删除第一个元素,删除头元素
228         public Object removeFirst(){
229             return remove(0);
230         }
231         //删除最后一个元素,尾元素
232         public Object removeLast(){
233             return remove(size-1);
234         }
235         //返回头元素
236         public Object getFirst(){
237             return get(0); 
238         }
239         //返回尾元素
240         public Object getLast(){
241             return get(size-1);
242         }
243         
244     //定义一个内部类描述双向列表的结点
245     private class Node{
246         Object data;
247         Node prev;   //指向前驱结点
248         Node next;   //指向后续结点
249         public Node(Object data, Node prev, Node next) {
250             super();
251             this.data = data;
252             this.prev = prev;
253             this.next = next;
254         }
255         
256         
257     }
258 }

测试类:

 1 package demo1;
 2 /**
 3  * 测试双向列表
 4  * @author ASUS
 5  *
 6  */
 7 public class TestDualLinkedList {
 8 
 9     public static void main(String[] args) {
10         //创建双向列表
11         MyDualLinkedList linkedList=new MyDualLinkedList();
12         
13         System.out.println(linkedList.getSize());
14         System.out.println(linkedList.isEmpty());
15         
16         linkedList.insert(0,"gg");
17         linkedList.insert(0,"jj");
18         linkedList.insert(1,"dd");
19         linkedList.insert(2,"mm");
20         
21         System.out.println(linkedList);
22         System.out.println("-------------------");
23         //测试是否包含某个元素及第一次出现的位置
24         System.out.println(linkedList.indexOf("jj"));
25         System.out.println(linkedList.contains("mm"));
26         System.out.println(linkedList.indexOf("MM"));
27         System.out.println(linkedList.indexOf("xx"));
28         System.out.println(linkedList.indexOf("gg"));
29         System.out.println("-------------------");
30         //删除指定的元素
31         System.out.println(linkedList.remove(1));
32         System.out.println(linkedList);
33         System.out.println(linkedList.remove("mm"));
34         System.out.println(linkedList);
35         System.out.println("-------------------");
36         //替换指定元素
37         System.out.println(linkedList.replace(0, "哈哈"));
38         System.out.println(linkedList);
39         //返回指定元素的
40         System.out.println(linkedList.get(0));
41         System.out.println("-------------------");
42         
43         //在指定元素前面加入
44         System.out.println(linkedList.insertBefore("哈哈", "前面"));
45         System.out.println(linkedList);
46         //后面
47         System.out.println(linkedList.insertAfter("哈哈", "后面"));
48         System.out.println(linkedList);
49         System.out.println("--------------------");
50         //头部尾部添加删除返回
51         linkedList.addFirst("头部");
52         linkedList.addLast("尾部");
53         System.out.println(linkedList);
54         System.out.println(linkedList.getFirst());
55         System.out.println(linkedList.getLast());
56         //删除头部尾部
57         linkedList.removeFirst();
58         linkedList.removeLast();
59         System.out.println(linkedList);
60     
61     }
62 
63}

 

 

运行截图:

技术分享图片

 

关于JAVA数据结构_线性表(通过双向链表实现)的学习

标签:最后一个元素   contain   相同   @override   args   插入元素   

原文:https://www.cnblogs.com/yumu77/p/13752281.html

(0)
(0)
   
举报
评论 一句话评论(0
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号