简单链表的实现
结构
删除和插入操作的时间复杂度是O(1),
class Node {
private E e;
private Node next = null;
public Node(E e) {
this.e = e;
}
}
add
直接在链表的末尾添加，因为没有下标，只能从表头遍历到尾部，然后添加。
public void add(E e) {
Node node = new Node(e);
if (header == null) {
header = node;
} else {
Node p = header;
while (p.next != null) {
p = p.next;
}
p.next = node;
}
size++;
}
insert
插入到表的第i项后面，先循环遍历i次，再在后面插入X,调整链就可以。
public void insert(int i,E e){
Node node = new Node(e);
Node p = header;
for (int j = 0; j < i; j++){
p = p.next;
}
node.next = p.next;
p.next = node;
size++;
}
delete
删除第i项，循环i次，找到要删除的项，调整链。
public void delete(int i){
if (i == 0){
header = header.next;
}else {
Node p = header;
for (int j = 1; j < i; j++){
p = p.next;
}
p.next = p.next.next;
}
size--;
}
具体实现
package com.yb.shujujiegou.lianbiao;
/**
* Created by 杨波 on 2017/5/2.
*/
public class MyLink<E> {
class Node {
private E e;
private Node next = null;
public Node(E e) {
this.e = e;
}
}
private Node header = null;
private int size = 0;
public int getSize(){
return size;
}
public void dispaly() {
Node p = header;
while (p != null) {
System.out.print(p.e + " ");
p = p.next;
}
System.out.println();
}
public void addFirst(E e) {
Node node = new Node(e);
node.next = header;
header = node;
size++;
}
public void deleteFirst() {
header = header.next;
size--;
}
public E get(int i) {
Node p = header;
for (int j = 0; j < i; j++) {
p = p.next;
}
return p.e;
}
public void add(E e) {
Node node = new Node(e);
if (header == null) {
header = node;
} else {
Node p = header;
while (p.next != null) {
p = p.next;
}
p.next = node;
}
size++;
}
public void insert(int i,E e){
Node node = new Node(e);
Node p = header;
for (int j = 0; j < i; j++){
p = p.next;
}
node.next = p.next;
p.next = node;
size++;
}
public void delete(int i){
if (i == 0){
header = header.next;
}else {
Node p = header;
for (int j = 1; j < i; j++){
p = p.next;
}
p.next = p.next.next;
}
size--;
}
public void swap(int i){
Node p = header;
for (int j = 1; j < i; j++){
p = p.next;
}
if (i == 0){
Node n = header.next;
header.next = header.next.next;
n.next = header;
header = n;
}else {
Node node1 = p.next;
Node node2 = p.next.next;
p.next = node2;
node1.next = node2.next;
node2.next = node1;
}
}
public boolean contains(E e){
Node p = header;
for (int j = 0; j < size; j++){
if (p.e == e){
return true;
}
p = p.next;
}
return false;
}
}