LinkList的两种实现方法

╰+攻爆jí腚メ 2021-12-22 01:57 315阅读 0赞

最近一段时间在看算法，发现实现链表有联众方法，本科的时候学习数据结构，对于链表来说，会先建立一个头结点，firstNode，而这个first结点本身是一个node，只不过值域为空，而next域则是指向随后的结点。而在Robert Sedgewick的算法书中，是另一种实现方法，first是一个指针，直接指向真正的第一个结点，而在头部插入新的结点时，先用一个oldFirst结点引用老的first，这样，插入的新节点的next域指向oldFirst，而first指向新的Node,这样不会造成循环。

1.本科数据结构类型的linklist

1 package Chapter1_1_3_LinkList;
      2 
      3 import java.util.Iterator;
      4 
      5 public class LinkList<Item> implements Iterable<Item>{
      6     private LinkNode<Item> first;
      7     
      8     private int size;
      9     
     10     
     11 public LinkList(){
     12     first=new LinkNode<Item>();
     13     first.setE(null);
     14     first.setNext(null);
     15     //first=null;
     16     size=0;
     17 }
     18 public void addHeadNode(Item e){
     19     LinkNode<Item> newNode=new LinkNode<Item>();
     20     newNode.setE(e);
     21     newNode.setNext(first.getNext());
     22     first.setNext(newNode);
     23     size++;
     24 }
     25 
     26 public Item removeNode(int n){
     27     LinkNode<Item> index=first;
     28     int i=0;
     29     while(i<n-1&&index.getNext()!=null){
     30         index=index.getNext();
     31         i++;
     32     }
     33     LinkNode<Item> removeNode=index.getNext();
     34     index.setNext(removeNode.getNext());
     35     Item e= removeNode.getE();
     36     
     37     size--;
     38     return e;
     39 }
     40 public void addNode(Item e, int n){
     41     LinkNode<Item> index=first;
     42     int i=0;
     43     while(i<n&&index.getNext()!=null){
     44         index=index.getNext();
     45         i++;
     46     }
     47     LinkNode<Item> newNode=new LinkNode<Item>();
     48     newNode.setE(e);
     49     newNode.setNext(index.getNext());
     50     index.setNext(newNode);
     51     size++;
     52 }
     53 public void addTailNode(Item e){
     54     LinkNode<Item> last=first;
     55     while(last.getNext()!=null)
     56         last=last.getNext();
     57     LinkNode<Item> newNode=new LinkNode<Item>();
     58     newNode.setE(e);
     59     newNode.setNext(last.getNext());
     60     last.setNext(newNode);
     61     size++;    
     62 }
     63 public Item removeHeadNode(){
     64     LinkNode<Item> firstNode=first.getNext();
     65     Item e=firstNode.getE();
     66     first=first.getNext();
     67     size--;
     68     return e;
     69 }
     70 public Item removeTailNode(){
     71     LinkNode<Item> lastpre=first;
     72     LinkNode<Item> last;
     73     while(lastpre.getNext().getNext()!=null)
     74         lastpre=lastpre.getNext();
     75         last=lastpre.getNext();
     76         Item e=last.getE();
     77     lastpre.setNext(null);
     78     size--;
     79     return e;
     80 }
     81 @Override
     82 public Iterator<Item> iterator() {
     83     // TODO Auto-generated method stub
     84     return null;
     85 }
     86 private class LinkListIterator implements Iterator<Item>{
     87     LinkNode<Item> index=first;
     88     
     89     @Override
     90     public boolean hasNext() {
     91         // TODO Auto-generated method stub
     92         if(index!=null)
     93             return true;
     94         else return false;
     95     }
     96 
     97     @Override
     98     public Item next() {
     99         // TODO Auto-generated method stub
    100         Item e=index.getE();
    101         index=index.getNext();
    102         return e;
    103     }
    104 
    105     @Override
    106     public void remove() {
    107         // TODO Auto-generated method stub
    108         System.out.println("no remove");
    109     }
    110     
    111 }
    112 }

这部分主要看addHeadNode的方法，其他方法因为原理差不多就没有修正。

2.书中方法实现LinkList

stack:

1 package Chapter1_1_3_LinkStack;
     2 
     3 public class LinkStack<Item> {
     4 private LinkNode<Item> top;
     5 private int size;
     6 public LinkStack(){
     7     top=null;
     8     size=0;
     9 }
    10 public void push(Item e){
    11     LinkNode<Item> newNode=new LinkNode<Item>();
    12     newNode.e=e;
    13     LinkNode<Item> oldTop=top;
    14     newNode.next=oldTop;
    15     top=newNode;
    16     size++;
    17 }
    18 public Item pop(){
    19     if(isEmpty())
    20     {
    21         System.out.println("Stack is Empty");
    22         return null;
    23     }
    24     Item e=top.e;
    25     top=top.next;
    26     size--;
    27     return e;
    28 }
    29 public boolean isEmpty(){
    30     if(top==null)
    31         return true;
    32     else return false;
    33 }
    34 public int getSize(){
    35     return size;
    36 }
    37 }

queue:

1 package Chapter1_1_3_LinkQueue;
     2 
     3 public class LinkQueue<Item> {
     4 private LinkNode<Item> head;
     5 //private LinkNode<Item> tail;
     6 private int size;
     7 public LinkQueue(){
     8     head=null;
     9     //tail=null;
    10     size=0;
    11 }
    12 public boolean isEmpty(){
    13     if(head==null)
    14         return true;
    15     else return false;
    16 }
    17 public void enqueue(Item e){
    18     LinkNode<Item> newNode=new LinkNode<Item>();
    19     LinkNode<Item> oldHead=head;
    20     newNode.element=e;
    21     newNode.next=oldHead;
    22     head=newNode;
    23     size++;
    24 }
    25 public Item dequeue(){
    26     if(isEmpty())
    27     {
    28         System.out.println("Queue is Empty");
    29         return null;
    30     }
    31     LinkNode<Item> tail=head;
    32     LinkNode<Item> preTail = head;
    33     while(tail.next!=null){
    34         preTail=tail;
    35         tail=tail.next;
    36     }
    37     
    38     Item e=tail.element;
    39     preTail.next=tail.next;
    40     if(size==1){
    41         head=null;
    42     }
    43     size--;
    44     return e;
    45 }
    46 public int getSize(){
    47     return size;
    48 }
    49 }

16:00:27

转载于:https://www.cnblogs.com/criseRabbit/p/3990932.html