上次写了简单的链表实现，这次完善了链表的功能并添加了头结点。
实现
代码语言：javascript复制class LinkedList<E>
{
private class Node
{
public E e;
public Node next;
public Node(E e,Node next)
{
this.e = e;
this.next = next;
}
public Node(E e) : this(e, null)
{
}
public Node() : this(default(E), null)
{
}
public override string ToString()
{
return e.ToString();
}
}
private Node dummyhead;
private int size;
public LinkedList()
{
dummyhead = new Node(default(E),null);
size = 0;
}
public int getSize()
{
return size;
}
public bool isEmpty()
{
return size == 0;
}
//在链表头添加新的元素e
public void addFirst(E e)
{
add(0, e);
}
//在链表的index位置添加新的元素e
public void add(int index,E e)
{
if (index < 0 || index > size)
throw new ArgumentException("Add failed. Illegal index.");
//找到索引位置的前一元素
Node prev = dummyhead;
for (int i = 0; i < index; i )
prev = prev.next;
Node node = new Node(e);
node.next = prev.next;
prev.next = node;
//prev.next = new Node(e, prev.next);
size ;
}
//在链表末尾添加新的元素e
public void addLast(E e)
{
add(size, e);
}
//获得链表的第index个位置的元素
public E get(int index)
{
if (index < 0 || index >= size)
throw new ArgumentException("Get failed.Illegal index.");
Node cur = dummyhead.next;
for (int i = 0; i < index; i )
cur = cur.next;
return cur.e;
}
//获得链表的第一个元素
public E getFirst()
{
return get(0);
}
//获得链表的最后一个元素
public E getLast()
{
return get(size - 1);
}
//修改链表的index位置的元素e
public void set(int index ,E e)
{
if (index < 0 || index >= size)
throw new ArgumentException("Set failed.Illegal index.");
Node cur = dummyhead.next;
for (int i = 0; i < index; i )
cur = cur.next;
cur.e = e;
}
//查找链表中是否存在元素e
public bool contains(E e)
{
Node cur = dummyhead.next;
while (cur != null)
{
if (cur.e.Equals(e)) return true;
cur = cur.next;
}
return false;
}
//从链表中删除指定位置的元素
public E remove(int index)
{
if (index < 0 || index >= size)
throw new ArgumentException("Remove failed.Illegal index.");
Node prev = dummyhead;
for (int i = 0; i < index; i )
prev = prev.next;
Node retNode = prev.next;
prev.next = retNode.next;
retNode.next = null;
size--;
return retNode.e;
}
//从链表中给删除第一个元素，返回删除的元素
public E removeFirst()
{
return remove(0);
}
public E removeLast()
{
return remove(size - 1);
}
public override string ToString()
{
StringBuilder sb = new StringBuilder();
Node cur = dummyhead.next;
while (cur != null)
{
sb.Append(cur "->");
cur = cur.next;
}
sb.Append("NULL");
return sb.ToString();
}
}写个测试类测试一下
测试
代码语言：javascript复制static void Main(string[] args)
{
LinkedList<int> linkedList = new LinkedList<int>();
for(int i = 0; i < 5; i )
{
linkedList.addFirst(i);
Console.WriteLine(linkedList);
}
linkedList.add(2, 666);
Console.WriteLine(linkedList);
linkedList.remove(2);
Console.WriteLine(linkedList);
linkedList.removeFirst();
Console.WriteLine(linkedList);
linkedList.removeLast();
Console.WriteLine(linkedList);
Console.ReadKey();
}结果
在这里插入图片描述测试了每个方法，和预期的一样
