单向链表
单向链表是链表的一种,它由多个结点组成,每个结点都由一个数据域和一个指针域组成,数据域用来存储数据,指针域用来指向其后继结点。链表的头结点的数据域不存储,指针域指向第一个存储数据的结点。
单向链表Api设计
类型 |
LinkList |
构造方法 |
LinstList() |
成员方法 |
1.public void clear():空置线性表 2.publicboolean isEmpty():判断线性表是否为空,是返回true,否返回false 3.public int length():获取线性表中元素的个数 4.public T get(int i):读取并返回线性表中的第i个元素的值 5.public void insert(T t):往线性表中添加一个元素 6.public void insert(int i,T t):在线性表的第i个元素之前插入一个值为t的数据元素。 7.public T remove(int i):删除并返回线性表中第i个数据元素 8.public int indexOf(T t):返回线性表中首次出现的指定的数据元素的位序号,若不存在,则 返回-1。 |
成员内部类 |
private class Node:结点类 |
成员变量 |
1.private Node head:记录首结点 2.private int N:记录链表的长度 |
代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176
| package com.bestrookie.link;
import java.util.Iterator;
public class LinkList<T> implements Iterable<T>{
private Node head;
private int N;
private class Node{ T item; Node next;
public Node(T item, Node next) { this.item = item; this.next = next; } }
public LinkList(){ this.head = new Node(null,null); this.N = 0; }
public void clean(){ head.next = null; this.N = 0; }
public boolean isEmpty(){ return N == 0; }
public int length(){ return N; }
public T get(int i){ Node n = head.next; for (int index = 0; index < i; index++){ n = n.next; } return n.item; }
public void insert(T t){ Node n = head; while (n.next != null){ n = n.next; } n.next = new Node(t,null); N++; }
public void insert(int i, T t){ Node prev = head; for (int index = 0;index <= i-1;index++){ prev = prev.next; } Node current = prev.next; prev.next = new Node(t,current); N++; }
public T remove(int i){ Node prev = head; for (int index = 0; index<= i-1; index++){ prev = prev.next; } Node current = prev.next; prev.next = current.next; N--; return current.item;
}
public int indexOf(T t){ Node n = head; for (int i = 0; n.next != null; i++) { n = n.next; if (n.item.equals(t)){ return i; } } return -1; } @Override public Iterator<T> iterator() { return new LIterator(); } private class LIterator implements Iterator{ private Node n; public LIterator(){ this.n = head; } @Override public boolean hasNext() { return n.next != null; }
@Override public Object next() { n = n.next; return n.item; } } }
|
测试
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
| package com.bestrookie.link;
public class TestLink { public static void main(String[] args) { LinkList<String> s1 =new LinkList<>(); s1.insert("姚明"); s1.insert("科比"); s1.insert("麦迪"); s1.insert("詹姆斯"); System.out.println(s1.length()); s1.insert(1,"库里"); System.out.println(s1.length()); for (String s : s1) { System.out.println(s); } System.out.println("================="); System.out.println("获取索引2的位置的数据"+s1.get(2)); String remove = s1.remove(3); System.out.println("删除索引3位置的数据并返回"+remove); s1.clean(); System.out.println(s1.length());
} }
|